Algorytm Floyda Warshalla - MarcinG121/INPGProject GitHub Wiki

Algorytm Floyda-Warshalla wykorzystuje metodę programowania dynamicznego. Służy do znajdowania najkrótszych ścieżek pomiędzy wszystkimi parami wierzchołków w grafie ważonym. Graf może zawierać gałęzie zarówno o dodatniej i o ujemnej długości, lecz nie może zawierać ujemnych cykli (cykli, w których suma wag krawędzi jest ujemna).

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 wierzchoł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[v1, v2] = { 0, gdy   v1 = v2 
                    w(v1, v2), gdy (v1, v2) ∈ E 
                    +∞, gdy (v1, v2) ∉ E }

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.

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]