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 různých obecných (kladný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ž je zřejmé, že odhad je optimální 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 .

Jiné Jazyky