Floyd

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 dij(k) oznacza długość najkrótszej spośród najkrótszej vi do vj o wierzchołkach pośrednich w zbiorze {v1,...,vk} Stąd:
dij(0)=Aij (połączenie przez jedną krawędź )
dij(k+1)=min{dij(k), di k+1(k)+dk+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 "*" oznacza nieskończoność:

Oto przebieg obliczeń:

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

k=1 d 1 2 3 4 5 6
1 0 2 4 * * *
2 * 0 * * * 4
3 * * 0 -2 3 *
4 * * * 0 * 2
5 * * * * 0 *
6 * 2 * * 1 0

k=2 d 1 2 3 4 5 6
1 0 2 4 * * 6
2 * 0 * * * 4
3 * * 0 -2 3 *
4 * * * 0 * 2
5 * * * * 0 *
6 * 2 * * 1 0

k=3 d 1 2 3 4 5 6
1 0 2 4 2 7 6
2 * 0 * * * 4
3 * * 0 -2 3 *
4 * * * 0 * 2
5 * * * * 0 *
6 * 2 * * 1 0

k=4 d 1 2 3 4 5 6
1 0 2 4 2 7 4
2 * 0 * * * 4
3 * * 0 -2 3 0
4 * * * 0 * 2
5 * * * * 0 *
6 * 2 * * 1 0

k=5 d 1 2 3 4 5 6
1 0 2 4 2 7 4
2 * 0 * * * 4
3 * * 0 -2 3 0
4 * * * 0 * 2
5 * * * * 0 *
6 * 2 * * 1 0

k=6 d 1 2 3 4 5 6
1 0 2 4 2 5 4
2 * 0 * * 5 4
3 * 2 0 -2 1 0
4 * 4 * 0 3 2
5 * * * * 0 *
6 * 2 * * 1 0

przykład algorytmu w Delphi - floyd.zip (1 kB )

Tomasz Lubiński