Nevíte, jak vybrat nejkratší cestu z vašeho místa do cíle?. Pak byste měli znát tento algoritmus.
- Floyd-Warshallův algoritmus se používá k nalezení nejkratších cest mezi všemi dvojicemi vrcholů v grafu, kde každá hrana v grafu má váhu, která je kladná nebo záporná.
- Největší výhodou použití tohoto algoritmu je, že všechny nejkratší vzdálenosti mezi libovolnými 2 vrcholy lze vypočítat v čase O(V3), kde V je počet vrcholů v grafu.
- Algoritmus Floyd-Warshall se také nazývá Floydův algoritmus, Roy-Floydův algoritmus, Roy-Warshallův algoritmus nebo algoritmus WFI.
- Tento algoritmus používá k nalezení nejkratších cest přístup dynamického programování.
Algoritmus
Pro graf s N vrcholy:
Krok 1: Inicializujte nejkratší cesty mezi libovolnými 2 vrcholy pomocí nekonečna.
Krok 2: Najděte všechny párové nejkratší cesty, které používají 0 mezilehlých vrcholů, pak najděte nejkratší cesty, které používají 1 mezilehlý vrchol, a tak dále… až do použití všech N vrcholů jako mezilehlých uzlů.
Krok 3: Minimalizujte nejkratší cesty mezi libovolnými 2 dvojicemi v předchozí operaci.
Krok 4: Pro libovolné 2 vrcholy (i,j) , je třeba vlastně minimalizovat vzdálenosti mezi touto dvojicí pomocí prvních K uzlů, takže nejkratší cesta bude: min(dist+dist,dist).
dist představuje nejkratší cestu, která využívá pouze prvních K vrcholů, dist představuje nejkratší cestu mezi dvojicí k,j. Jako nejkratší cesta bude sloučena nejkratší cesta z i do k, pak z k do j.
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
dist = min( dist, dist + dist );
}
}
}
Příklad
Nechť je daný graf:
Postupujte podle následujících kroků a najděte nejkratší cestu mezi všemi dvojicemi vrcholů.
- Vytvořte matici
A0o dimenzin*n, kde n je počet vrcholů. Řádek a sloupec jsou indexovány jako i a j. i a j jsou vrcholy grafu.
Každá buňka A je vyplněna vzdáleností z vrcholu ith do vrcholu jth. Pokud neexistuje cesta z vrcholu ith do vrcholu jth, buňka se ponechá jako nekonečná.
2. Nyní vytvořte matici A1 pomocí matice A0. Prvky v prvním sloupci a prvním řádku ponechte tak, jak jsou. Zbývající buňky vyplníme následujícím způsobem:
Nechť k je mrazivý vrchol nejkratší cesty ze zdroje do cíle. V tomto kroku je k prvním vrcholem. A je vyplněna (A + A) if (A > A + A).
Tedy pokud je přímá vzdálenost od zdroje k cíli větší než cesta přes vrchol k, pak je buňka vyplněna A + A.
V tomto kroku je k vrcholem 1. Vypočítáme vzdálenost ze zdrojového vrcholu do cílového vrcholu přes tento vrchol k.
Např: Pro A1 je přímá vzdálenost z vrcholu 2 do 4 4 a součet vzdáleností z vrcholu 2 do 4 přes vrchol (tj. z vrcholu 2 do 1 a z vrcholu 1 do 4) je 7. Protože 4 < 7, A0 je naplněn 4.
3. Podobným způsobem je A2 vytvořen pomocí A3. Prvky ve druhém sloupci a druhém řádku se ponechají tak, jak jsou.
V tomto kroku je k druhým vrcholem (tj. vrcholem 2). Zbývající kroky jsou stejné jako v kroku 2.
4. Podobně se vytvoří také A3 a A4.
A4 udává nejkratší cestu mezi každou dvojicí vrcholů.
Pokud si nevíte rady s výběrem nejkratší cesty, použijte k jejímu nalezení níže uvedený kód. Zadejte však správné vzdálenosti.
Časová složitost
Jsou zde tři smyčky. Každá smyčka má konstantní složitost. Časová složitost Floydova-Warshallova algoritmu je tedy O(n3).
Prostorová složitost
Prostorová složitost Floydova-Warshallova algoritmu je O(n2).