Po wykonaniu takich kroków długości najkrótszych ścieżek są już wyliczone.
Wydajność algorytmu Złożoność obliczeniowa: Złożoność pamięciowa:
Zapis w pseudokodzie Dla grafu i funkcji wagowej otrzymamy tablicę odległości pomiędzy wierzchołkami i
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
Przypisy
Bibliografia
Linki zewnętrzne [dostęp 2025-12-20].
Floyda-Warshalla Kategoria:Programowanie dynamiczne