Algorytm ten służy do wyznaczania najmniejszej odległości pomiędzy wszystkimi parami wierzchołków w skierowanym grafie bez cykli o ujemnej długości.
Warunek nieujemności cyklu jest spowodowany faktem, że w grafie o ujemnych cyklach najmniejsza odległość między niektórymi wierzchołkami jest nieokreślona, ponieważ zależy od liczby przejść w cyklu.
Algorytmu tego można również użyć do obliczenia domknięcia przechodniego relacji binarnej przedstawionej w postaci grafu skierowanego G. Wówczas domknięcie przechodnie definiuje się jako: Eⁿ={(x,y): istnieje w G droga o niezerowej długości od x do y} (przy tej definicji każda krawędź ma wagę 1).
Dla podanego grafu macierz A dla każdej pary wierzchołków u i v zawiera wagę krawędzi (u,v), przy czym jeśli krawędź (u,v) nie istnieje, to przyjmujemy, że jej waga wynosi nieskończoność.
Algorytm Floyda opiera się na następującym spostrzeżeniu. Niech d_ij^(k) oznacza długość najkrótszej spośród dróg v_i do v_j o wierzchołkach pośrednich w zbiorze {v₁,...,v_k} Stąd:
d_ij⁽⁰⁾=A_ij (połączenie przez jedną krawędź)
d_ij^(k+1)=min{d_ij^(k), d_{i k+1}^(k)+d_{k+1 j}^(k)}


Pseudokod wygląda następująco:(n- liczba wierzchołków)

begin;
for i:=1 to n do
 for j:=1 to n do d(i,j)=A(i,j);
for i:=1 to n do d(i,i)=0;
for k:=1 to n do
 for i:=1 to n do
  for j:=1 to n do
  d(i,j)=min( d(i,j), d(i,k)+d(k,j) );
end;

Dla przykładu oto graf i jego reprezentacja w postaci macierzy wag krawędzi.
symbol "n" lub "*" oznacza nieskończoność:
Oto przebieg obliczeń:

d(i,j)=A(i,j) d 1 2 3 4 5 6 1 0 2 4 n n n 2 n 0 n n 4 n 3 n n 0 -2 3 n 4 1 n n 0 n 2 5 n n n n 0 n 6 n 2 n n 1 0	k=1 d 1 2 3 4 5 6 1 0 2 4 n n n 2 n 0 n n 4 n 3 n n 0 -2 3 n 4 1 3 5 0 n 2 5 n n n n 0 n 6 n 2 n n 1 0	k=2 d 1 2 3 4 5 6 1 0 2 4 n 6 n 2 n 0 n n 4 n 3 n n 0 -2 3 n 4 1 3 5 0 7 2 5 n n n n 0 n 6 n 2 n n 1 0
k=3 d 1 2 3 4 5 6 1 0 2 4 2 6 n 2 n 0 n n 4 n 3 n n 0 -2 3 n 4 1 3 5 0 7 2 5 n n n n 0 n 6 n 2 n n 1 0	k=4 d 1 2 3 4 5 6 1 0 2 4 2 6 4 2 n 0 n n 4 n 3 -1 1 0 -2 3 0 4 1 3 5 0 7 2 5 n n n n 0 n 6 n 2 n n 1 0	k=5 d 1 2 3 4 5 6 1 0 2 4 2 6 4 2 n 0 n n 4 n 3 -1 1 0 -2 3 0 4 1 3 5 0 7 2 5 n n n n 0 n 6 n 2 n n 1 0
	k=6 d 1 2 3 4 5 6 1 0 2 4 2 5 4 2 n 0 n n 4 n 3 -1 1 0 -2 1 0 4 1 3 5 0 3 2 5 n n n n 0 n 6 n 2 n n 1 0

Komentarze