Algorytm Floyda-Warshalla służy do znajdowania najkrótszych ścieżek pomiędzy wszystkimi parami wierzchołków w graf ważonym.

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:
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 sie 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) \]
Złożoność pamięciowa: \[O(V^2) \]

Zapis w pseudokodzie

Dla grafu G i funkcji wagowej w otrzymamy tablicę d[1][2] 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]


Publikacja wraz ze zdjęciami jest udostępniona w Encyklopedii "Zgapedia" części portalu zgapa.pl. Treść objęta jest licencją GNU FDL Wolnej Dokumentacji w wersji 1.3 lub dowolnej pózniejszej opublikowanej przez Free Software Foundation i została ona opracowana na podstawie Wikipedii, tutaj możesz znaleźć artykuł źródłowy oraz autorów. Warunki użytkowania Encyklopedii znajdziesz na tej stronie.