Floyd Warshall Algoritması

Giriş
Bu algoritma iç içe 3 tane döngü kullandığı için O (N^3) yani n küp.

Bu algoritma ile iki düğüm arasındaki cost eksi değer olsa bile sorun çıkmıyor. Dolayısıyla Dijkstra'nın Shortest Path algoritmasının kullanılamadığı yerlerde kullanılabilir.

Önce ilklendirmek için şöyle yaparız.

for(int i = 0; i < N; i++)
  for(int j = 0; j <N; j++)
    adjMat[i][j]=INF;

İkinci adımda bildiğimiz mesafeleri adjMat [][] alanlarına yerleştiririz.

Algoritma'nın en önemli kısmı şöyle

for(int k = 0; k < N; ++k) {
  for(int i = 0; i < N; ++i) {
    for(int j = 0; j < N; ++j) {
      adjMat[i][j] = Math.min(adjMat[i][j], adjMat[i][k] + adjMat[k][j]);
    }
  }
}

En içteki iki döngü ile tüm matris dolaşılır. En dıştaki döngü i'den j'ye giderken iki tane farklı yolu denemek içindir. i'->j yolu ile (i->k + k->j) yolu karşılaştırılır.

Örnek 1
Belli nodlara uğramak zorunda olduğumu en kısa yolu bulmak için şöyle yaparız.

//Precomputation: Find all pairs shortest paths, e.g. using Floyd-Warshall
n = number of nodes
for i=1 to n: for j=1 to n: d[i][j]=INF
for k=1 to n:
    for i=1 to n:
        for j=1 to n:
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])
//That *really* gives the shortest distance between every pair of nodes! :-)

//Now try all permutations
shortest = INF
for each permutation a[1],a[2],...a[k] of the 'mustpass' nodes:
    shortest = min(shortest, d['start'][a[1]]+d[a[1]][a[2]]+...+d[a[k]]['end'])
print shortest