Floydův–Warshallův algoritmus

Floydův–Warshallův algoritmus (známý také jako Royův–Floydův algoritmus) je počítačový algoritmus používaný pro nalezení nejkratších cest v orientovaném grafu s hranami obecných vah. Jediný průchod algoritmu spočte nejkratší cestu mezi všemi dvojicemi vrcholů. Floydův–Warshallův algoritmus je typickým příkladem dynamického programování. Algoritmus poprvé popsali Robert Floyd a Stephen Warshall.

Algoritmus

Floydův–Warshallův algoritmus porovnává všechny možné cesty v grafu mezi všemi dvojicemi vrcholů. Pracuje tak, že postupně vylepšuje odhad na nejkratší cestu do té doby, než projde všechny možnosti.

Mějme graf ${\displaystyle G}$ s vrcholy ${\displaystyle V}$ očíslovanými 1 až N. Dále mějme funkci ${\displaystyle nejkratsiCesta(i,j,k)}$, která vrací nejkratší možnou cestu z ${\displaystyle i}$ do ${\displaystyle j}$ s použitím pouze vrcholů 1 až ${\displaystyle k}$ jako mezivrcholů. Pomocí této funkce chceme najít nejkratší cestu mezi všemi dvojicemi ${\displaystyle i}$ a ${\displaystyle j}$ s použitím mezivrcholů 1 až ${\displaystyle k+1}$.

Na nejkratší cestu máme dva kandidáty: buď je nejkratší cesta v množině vrcholů ${\displaystyle (1...k)}$, nebo existuje cesta jdoucí z ${\displaystyle i}$ do ${\displaystyle k+1}$, a poté z ${\displaystyle k+1}$ do ${\displaystyle j}$, která je lepší (kratší) než ta stávající. Nejlepší cesta z ${\displaystyle i}$ do ${\displaystyle j}$ používající pouze vrcholy 1 až ${\displaystyle k}$ je definována funkcí ${\displaystyle nejkratsiCesta(i,j,k)}$. Délka nejlepší cesty z ${\displaystyle i}$ do ${\displaystyle k+1}$ a poté do ${\displaystyle j}$ je pak zřejmě součet délek nejkratší cesty z ${\displaystyle i}$ do ${\displaystyle k+1}$ a nejkratší cesty z ${\displaystyle k+1}$ do ${\displaystyle j}$.

Funkci ${\displaystyle nejkratsiCesta(i,j,k)}$ pak můžeme rekurzivně definovat takto:

${\displaystyle nejkratsiCesta(i,j,k)=min(nejkratsiCesta(i,j,k-1),nejkratsiCesta(i,k,k-1)+nejkratsiCesta(k,j,k-1));}$

${\displaystyle nejkratsiCesta(i,j,0)=cenaHrany(i,j);}$

Algoritmus nejprve spočte ${\displaystyle nejkratsiCesta(i,j,0)}$ pro všechny dvojice i a j, poté pro všechny dvojice spočte ${\displaystyle nejkratsiCesta(i,j,1)}$ atp. dokud nedosáhne k = N, kdy jsme našli nejkratší cesty pro všechny dvojice vrcholů ${\displaystyle i}$ a ${\displaystyle j}$ v grafu ${\displaystyle G}$. Asymptotická časová složitost algoritmu je ${\displaystyle O(N^{3})}$.

Při počítání k-té úrovně můžeme přepsat informace vytvořené (k – 1)-ní úrovní, což je optimalizace. Algoritmus v obou případech používá kvadratické množství paměti vůči počtu vrcholů grafu. Asymptotická paměťová složitost je tedy ${\displaystyle O(N^{2})}$.

Pseudokód

 1 // Předpokládáme funkci cenaHrany(i, j) vracející cenu hrany z i do j
 2 // (pokud hrana neexistuje, cenaHrany = nekonečno)
 3 // Dále, N je počet vrcholů a cenaHrany(i, i) = 0 
 4 
 5 int cesta[][]; // Dvourozměrné pole. V každém kroku algoritmu je cesta[i][j] 
 6                // nejkratší cesta z i do j použitím 1. až k-té hrany.
 7                // Všechny hrany cesta[i][j] jsou inicializovány funkcí 
 8                // cenaHrany(i,j);            
 9
10 procedure FloydWarshall ()
11    for ${\displaystyle {\mathit {k}}:=1}$ to ${\displaystyle {\mathit {N}}}$
12    begin
13       foreach ${\displaystyle {\mathit {(i,j)}}}$ in ${\displaystyle (1..N)}$
14       begin
15          cesta[i][j] = min(cesta[i][j], cesta[i][k] + cesta[k][j]);
16       end
17    end
18 endproc

Implementace

• v Perlu je součástí modulu Graph
• v Pythonu je součástí balíku NetworkX

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Floyd-Warshall algorithm na anglické Wikipedii.

Související články

• Dijkstrův algoritmus
• Bellmanův-Fordův algoritmus
• Johnsonův algoritmus

Externí odkazy

• Obrázky, zvuky či videa k tématu Floydův-Warshallův algoritmus na Wikimedia Commons
• Interaktivní animace práce Floydova–Warshallova algoritmu