Algorytm Floyda-Warshalla

Szablon:Dopracować Szablon:Algorytm infobox Algorytm Floyda-Warshalla wykorzystujący metodę programowania dynamicznego algorytm służący do znajdowania najkrótszych ścieżek pomiędzy wszystkimi parami wierzchołków w grafie ważonymSzablon:Odn. Graf może zawierać gałęzie zarówno o dodatniej i o ujemnej wadze („długości”), lecz nie może zawierać ujemnych cykli (cykli, w których suma wag krawędzi jest ujemna).

Opis algorytmu

Algorytm Floyda-Warshalla korzysta z tego, że jeśli najkrótsza ścieżka pomiędzy wierzchołkami $v_1$ i $v_2$ prowadzi przez wierzchołek $u,$ to jest ona połączeniem najkrótszych ścieżek pomiędzy wierzchołkami $v_1$ i $u$ oraz $u$ i $v_2.$ 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 $(v_1,v_2)$ ich odległość wynosi:

$d[v_1,v_2]=\{\begin{array}{cc}0,& \text{gdy}{v}_1=v_2\\ w(v_1,v_2),& \text{gdy}(v_1,v_2)\in E\\ +\mathrm{\infty },& \text{gdy}(v_1,v_2)\notin E\end{array}$

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.

Wydajność algorytmu

• Złożoność obliczeniowa: $O(|V{|}^3)$Szablon:Odn
• Złożoność pamięciowa: $O(|V{|}^2)$Szablon:Odn

Zapis w pseudokodzie

Dla grafu $G$ i funkcji wagowej $w$ otrzymamy tablicę $d[v_1][v_2]$ odległości pomiędzy wierzchołkami $v_1$ i $v_2.$

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ż

• algorytm Johnsona
• problem najkrótszej ścieżki

Bibliografia

• Szablon:Cytuj książkę