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ší 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ův–Warshallův algoritmus je typickým příkladem dynamického programování. Algoritmus poprvé popsali Robert Floyd a Stephen Warshall.

Algoritmus [editovat]

Tato část článku potřebuje úpravy.

Můžete Wikipedii pomoci tím, že ji vhodně vylepšíte. Jak by měly články vypadat, popisují stránky Vzhled a styl, Encyklopedický styl a Odkazy.

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ž 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^3)$ .

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^2)$ .

Pseudokód [editovat]

 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