ALG 5

10.5. Algorytm Floyda 255

•    W/iJ]~wartość przypisana krawędzi lub⁰⁰ (inaczej: bardzo dużą liczba);

•    wartość optymalnej drogi będzie zapamiętywana w matrycy D\

Ideę algorytmu w zrozumiały sposób prezentuje następujący przykład:

Załóżmy, że szukamy optymalnej drogi od / do j. W tym celu „przechadzamy” się po grafie, próbując ewentualnie znaleźć inny, pośredni wierzchołek k, którego „wbudowanie” w drogę umożliwiłoby otrzymanie lepszego wyniku niż już obliczone Dfi, j] Znajdujemy pewne k i zadajemy pytanie: czy przejście przez wierzchołek k poprawi nam w'ynik. czy nie? Popatrzmy na rysunek 10 - 8, który przedstawia odpowiedź na to pytanie w nieco bardziej poglądowej formie niż goły wzór matematyczny (przedstawiony obok).

Rys. W - H. Aigorvtm Floyda <!)■ '

Jest oczywiste, że w przypadku większej ilości takich „optymalnych” wierzchołków pośrednich należy wybrać najlepszy z nich!

Przedstawiony poniżej program jest najprostszą formą algorytmu Floyda, która wyłącznie oblicza wartość optymalnej drogi, ale jej nic zapamiętuje.

floyd.cpp

void floydtint g[n] [n] )

(

fortint k=0;k<n;k++) for(int i-0;i<n;i++) fortint j=0;j<n;i++)

g[i][j]-min( gli][j], g[i][k]+g[k)[j]);

)

Popatrzmy na rysunek 10 - 9, który przedstawia przykład wyboru optymalnej drogi przez algorytm Floyda.

Załóżmy, że interesuje nas optymalna droga od wierzchołka nr 0 do wierzchołka numer 4. Z uwagi na dość prostą topografię grafu, widać, że mamy do wyboru dwie drogi: 0-1-4 i nieco dłuższą: 0-I-2-4.

Elementarne obliczenia wykazują, że druga trasa jest efektywniejsza (koszt: 45) od pierwszej (koszt: 50).