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
![ikona](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2c/Broom_icon.svg/48px-Broom_icon.svg.png)
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 s vrcholy očíslovanými 1 až N. Dále mějme funkci , která vrací nejkratší možnou cestu z do s použitím pouze vrcholů 1 až jako mezivrcholů. Pomocí této funkce chceme najít nejkratší cestu mezi všemi dvojicemi a s použitím mezivrcholů 1 až .
Na nejkratší cestu máme dva kandidáty: buď je nejkratší cesta v množině vrcholů , nebo existuje cesta jdoucí z do , a poté z do , která je lepší (kratší) než ta stávající. Nejlepší cesta z do používající pouze vrcholy 1 až je definována funkcí . Délka nejlepší cesty z do a poté do je pak zřejmě součet délek nejkratší cesty z do a nejkratší cesty z do .
Funkci pak můžeme rekurzivně definovat takto:
Algoritmus nejprve spočte pro všechny dvojice i a j, poté pro všechny dvojice spočte atp. dokud nedosáhne k = N, kdy jsme našli nejkratší cesty pro všechny dvojice vrcholů a v grafu . Asymptotická časová složitost algoritmu je .
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 .
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 to 12 begin 13 foreach in 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
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