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 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); 910 procedure FloydWarshall ()11 forto
12 begin13 foreach
in
14 begin15 cesta[i][j] = min(cesta[i][j], cesta[i][k] + cesta[k][j]);16 end17 end18 endproc
Implementace
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