Algorytm Floyda-Warshalla
Z Wikipedii
Niniejszy artykuł jest częścią cyklu teoria grafów.
 |
|
Najważniejsze pojęcia Wybrane klasy grafów Algorytmy grafowe Zagadnienia przedstawiane jako problemy grafowe Inne zagadnienia |
| edytuj ten szablon |
Algorytm Floyda-Warshalla służy do znajdowania najkrótszych ścieżek pomiędzy wszystkimi parami wierzchołków w grafie ważonym.
[edytuj] Opis algorytmu
Algorytm Floyda-Warshalla korzysta z tego, że jeśli najkrótsza ścieżka pomiędzy wierzchołkami v1 i v2 prowadzi przez wierzchołek u, to jest ona połączeniem najkrótszych ścieżek pomiędzy wierchołkami v1 i u oraz u i v2. Na początku działania algorytmu inicjowana jest tablica długości najkrótszych ścieżek, tak że dla każdej pary wierzchołków (v1,v2) ich odległość wynosi:
![d[v_1,\,v_2]=\begin{cases} 0, & \mbox{gdy}\ v_1=v_2\\ w(v_1,\,v_2), & \mbox{gdy}\ (v_1,\,v_2)\in E \\ +\infty, & \mbox{gdy}\ (v_1,\,v_2)\not\in E\end{cases}](../../../math/1/6/5/165ad3070e3bf2c0d2b3edd034b468e0.png)
Algorytm jest dynamiczny i w kolejnych krokach włącza do swoich obliczeń ścieżki przechodzące przez kolejne wierzchołki. Tak więc w k-tym kroku algorytm zajmie się sprawdzaniem dla każdej pary wierzchołków, czy nie da się skrócić (lub utworzyć) ścieżki pomiędzy nimi przechodzącej przez wierzchołek numer k (kolejność wierzchołków jest obojętna, ważne tylko, żeby nie zmieniała się w trakcie działania programu). Po wykonaniu |V| takich kroków długości najkrótszych ścieżek są już wyliczone.
[edytuj] Wydajność algorytmu
- Złożoność obliczeniowa:
- Złożoność pamięciowa:
[edytuj] Zapis w pseudokodzie
Dla grafu G i funkcji wagowej w otrzymamy tablicę d[v1][v2] odległości pomiędzy wierzchołkami v1 i v2.
Floyd-Warshall(G,w)
dla każdego wierzchołka v1 w V[G] wykonaj
dla każdego wierzchołka v2 w V[G] wykonaj
d[v1][v2] = nieskończone
poprzednik[v1][v2] = niezdefiniowane
d[v1][v1] = 0
dla każdej krawędzi (v1,v2) w E[G]
d[v1][v2] = w(v1,v2)
poprzednik[v1][v2] = v1
dla każdego wierzchołka u w V[G] wykonaj
dla każdego wierzchołka v1 w V[G] wykonaj
dla każdego wierzchołka v2 w V[G] wykonaj
jeżeli d[v1][v2] > d[v1][u] + d[u][v2] to
d[v1][v2] = d[v1][u] + d[u][v2]
poprzednik[v1][v2] = poprzednik[u][v2]
Zobacz też: problem najkrótszej ścieżki, algorytm Johnsona
