Tekst źródłowy strony Algorytm Floyda-Warshalla

{{dopracować|więcej przypisów=2014-06}}
{{Algorytm infobox
 |nazwa            = Algorytm Floyda-Warshalla
 |grafika          = 
 |wielkość grafiki = 
 |opis grafiki     = 
 |rodzaj           = [[problem najkrótszej ścieżki]]
 |struktura        = [[graf skierowany]]
 |czas             = <math>O(|V|^3)</math>
 |pamięć           = <math>O(|V|^2)</math>
}}
'''Algorytm Floyda-Warshalla''' wykorzystujący metodę [[programowanie dynamiczne|programowania dynamicznego]] [[algorytm]] służący do znajdowania najkrótszych ścieżek pomiędzy wszystkimi parami [[Wierzchołek (teoria grafów)|wierzchołków]] w [[graf (matematyka)|grafie]] ważonym{{odn|Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein|s=627}}. 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 <math>v_1</math> i <math>v_2</math> prowadzi przez wierzchołek <math>u,</math> to jest ona połączeniem najkrótszych ścieżek pomiędzy wierzchołkami <math>v_1</math> i <math>u</math> oraz <math>u</math> i <math>v_2.</math> 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 <math>(v_1,v_2)</math> ich odległość wynosi:
: <math>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)\notin E
\end{cases}</math>

Algorytm jest [[Programowanie dynamiczne|dynamiczny]] i w kolejnych krokach włącza do swoich obliczeń ścieżki przechodzące przez kolejne wierzchołki. Tak więc w <math>k</math>-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 <math>k</math> (kolejność wierzchołków jest obojętna, ważne tylko, żeby nie zmieniała się w trakcie działania programu). Po wykonaniu <math>|V|</math> takich kroków długości najkrótszych ścieżek są już wyliczone.

=== Wydajność algorytmu ===
* Złożoność obliczeniowa: <math>O(|V|^3)</math>{{odn|Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein|s=627}}
* Złożoność pamięciowa: <math>O(|V|^2)</math>{{odn|Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein|s=629}}

== Zapis w pseudokodzie ==
Dla grafu <math>G</math> i funkcji wagowej <math>w</math> otrzymamy tablicę <math>d[v_1][v_2]</math> odległości pomiędzy wierzchołkami <math>v_1</math> i <math>v_2.</math>

 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 ==
{{Przypisy}}

== Bibliografia ==
* {{cytuj książkę |autor = Thomas H. Cormen |autor2 = Charles E. Leiserson |autor3 = Ronald L. Rivest |autor4 = Clifford Stein |tytuł = Wprowadzenie do algorytmów |wydawca = WNT |rok = 2007 |wydanie = |odn = {{odn/id|Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein}}}}
{{Teoria grafów}}

[[Kategoria:Algorytmy grafowe|Floyda-Warshalla]]
[[Kategoria:Programowanie dynamiczne]]