Floyd-Warshallův algoritmus

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

[editovat] Algoritmus

Floyd–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ž je zřejmé, že odhad je optimální.

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

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

Funkci nejkratsiCesta(i,j,k) pak můžeme rekurzivně definovat takto:

nejkratsiCesta(i,j,k) = min(nejkratsiCesta(i,j,k − 1),nejkratsiCesta(i,k,k − 1) + nejkratsiCesta(k,j,k − 1));

nejkratsiCesta(i,j,0) = cenaHrany(i,j);

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

Při počítání k-té úrovně můžeme přepsat informace vytvořené (k - 1). úrovní. Algoritmus pak používá kvadratické množství paměti vůči počtu vrcholů grafu. Asymptotická paměťová složitost je tedy O(N²).

[editovat] 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 k: = 1 to N
12    begin
13       foreach (i,j) in (1..N)
14       begin
15          cesta[i][j] = min(cesta[i][j], cesta[i][k] + cesta[k][j]);
16       end
17    end
18 endproc

[editovat] Implementace

• v Perlu je součástí modulu Graph
• v Javascript je k dispozici na [1]
• v Pythonu je součástí balíku NetworkX
• v C++ je k dispozici na ece.rice.edu

[editovat] Související články

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

[editovat] Externí odkazy

• Interaktivní animace práce Floyd–Warshallova algoritmu

Tento článek je zčásti nebo zcela založen na překladu článku Floyd-Warshall algorithm na anglické Wikipedii. Číslo revize nebylo určeno.