Rešitev: Floyd-Warshallov algoritem

Iz MaFiRaWiki

Naloga: Floyd-Warshallov algoritem

Floyd-Warshallov algoritem deluje na principu dinamičnega programiranja. Z njegovo pomočjo rešujemo problem iskanja najkrajših poti v grafu. Pri tem je graf lahko usmerjen,teže povezav pa so lahko tudi negativne,le negativnih ciklov ne sme biti. Kot vhodne podatke damo matriko tež na povezavah, za rezultat pa dobimo matriko, v kateri je v i-ti vrstici in j-tem stolpcu teža najkrajše poti med i-tim in j-tim vozliščem.


Rekurzivna enačba:

 
d(i,j; 0) = w(i,j) 
         ...teža povezave med i in j
d(i,j; k) = min{d(i,j; k-1), d(i,k; k-1)+d(k,j; k-1)} 
        ...1.možnost: k ni vmesno vozlišče na poti med i in j, torej je najkrajša pot 
                             med i in j preko {1,...,k} enaka najkrajši poti preko {1,...,k-1}.
        ...2.možnost: k je vmesno vozlišče na poti med i in j, torej je najkrajša pot 
                             med i in j preko {1,...,k} enaka vsoti poti med i in k ter k in j,
                              ki obe potekata preko{1,...,k-1}.

Algoritem:

 
FloydWarshall[AA_]:=
    Module[{A=AA,k,j,i},
                  For[k=1,k<5,k=k+1,
                  For[j=1,j<5,j=j+1,
                  For[i=1,i<5,i=i+1,
                  If[A[[i,j]]>A[[i,k]]+A[[k,j]],
                     A[[i,j]]=A[[i,k]]+A[[k,j]],
                     A[[i,j]]=A[[i,j]]]]]];
             Return[A//MatrixForm]];

Primer:

A={{0,5,Infinity,2},{Infinity,0,6,Infinity},{Infinity,3,0,7},{8,1,Infinity, 0}};
A//MatrixForm
 

\begin{bmatrix}   0&5&00&2\\   00&0&6&00\\   00&3&0&7\\   8&1&00&0\\\end{bmatrix}


 FloydWarshall[A]

Rezultat:

\begin{bmatrix}   0&3&9&2\\   21&0&6&13\\   15&3&0&7\\   8&1&7&0\\\end{bmatrix}
Osebna orodja