Célunk egy adott élsúlyozott gráf minden rendezett csúcspárjára a két csúcs közti legrövidebb út megkeresése. Irányított gráf esetén megengedünk negatív éleket, negatív összsúlyú köröket azonban nem, irányítatlan esetben negatív éleket sem engedünk meg.

Megkereshetjük úgy, hogy egy kezdőcsúcsból kiinduló legrövidebb utakat kereső algoritmust egyenként végrehajtunk minden csúcson. Ha az élsúlyok nemnegatívok, Dijkstra algoritmusát alkalmazhatjuk. Az algoritmus által használt prioritásos sort bináris kupac segítségével reprezentáljuk, akkor a futásidő ritka gráfokra $O(n(n + m) \cdot log \space n) = O(n^2 \cdot log \space n)$, sűrű gráfokra $O(n^3 \cdot log \space n)$. Ha negatív élsúlyokat is megengedünk a gráfban, a Bellman–Ford-algoritmust kell minden csúcsra egyszer végrehajtanunk. Ritka gráfok esetén a futási idő: $O(n \cdot n \cdot m) = O(n^3)$, sűrű gráfokra $O(n^4)$.

Láthatjuk, hogy sűrű gráfok esetén a fenti módszerek egyike sem túl hatékony, ezért egy olyan módszert használunk, ami minden gráf esetén $\Theta (n^3)$ költséggel működik.

Floyd-Warshall algoritmus:

Az algoritmus a gráfok csúcsmátrixos reprezentációjára épül. Megengedünk negatív élsúlyokat, de negatív összsúlyú köröket nem. Ha a gráf tartalmaz negatív összsúlyú kört, akkor a főátlóban negatív értékek jelennek meg és ezt az algoritmus ellenőrzi is.

Az egyes csúcsok közötti távolságok számításához egy $D$ mátrixot fogunk használni. $D_{ij}$ az $i$ és $j$ csúcs közti optimális út hosszát tartalmazza. Egy $\pi$ mátrixban a közvetlen megelőző csúcsokat tároljuk. $\pi_{ij}$ az $i$ és $j$ csúcs között vezető optimális úton, $j$ csúcs közvetlen megelőzőjét tartalmazza.

Az optimális utakat úgynevezett belső csúcsok mentén keressük. Egy $p =< v_{1}, v_{2}, ..., v_{k}>$ út belső csúcsa minden $v_{1}$-től és $v_{k}$-tól különböző csúcs.

Az algoritmus mátrixpárok sorozatát állítja elő 0-tól $n$-ig. $n$ lépésben határozza meg a csúcspárok közti legrövidebb utakat. A $k$-adik lépés után a $D^{(k)}_{ij}$ az $i$ és $j$ csúcsok között lévő optimális út hosszát tartalmazza. Tehát a $D^{(0)}$ mátrix megegyezik a gráf csúcsmátrixával, a $D^{(n)}$ mátrix a kiszámítandó $D$ mátrixal és a $\pi^{(n)}$ mátrix pedig a kiszámítandó $\pi$ mátrixszal. A $D$ és $\pi$ mátrixok kiszámításához nem kell segédmátrixokat tárolni, mivel a $k$-adik sor és $k$-adik oszlop a $k - 1$ és $k$-adik lépés között nem változik meg, hiszen a $k$ címkéjű csúcsból saját magán keresztül nem találhatunk rövidebb utat sehova, valamint a $k$ címkéjű csúcsba sem találhatunk legrövidebb utat önmagán keresztül semelyik másik csúcsból sem. Az egyes csúcsok közötti legrövidebb utakat a $\pi^{(n)}$ mátrix alapján meg tudjuk határozni.

Működése:

A feladatok megoldása során minden lépésben felrajzoljuk a mátrixokat. Ha a gráf irányítatlan, akkor a mátrixok a főátlóra szimmetrikusak. A $k$-adik lépésben végigmegyünk $D$ mátrix celláin, és megnézzük, hogy az $(i, j)$ cella esetén $(i, k)$ és $(k, j)$ cellák összege optimálisabb-e, ha igen, akkor módosítjuk az értékét. Fontos, hogy a $k$-adik lépésben a $k$-adik oszlop és sor, soha nem változik meg.

Műveletigény:

• $MT(n) \in \Theta(n^3)$
• $mT(n) \in \Theta(n^2)$