: index | programowanie | webmastering | algorytmika | download | projekty | słownik | grafika | flash | linki :

a l g o r y t m y > grafy >

A L G O R Y T M   F L O Y D A - W A R S H A L L A

 

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 29 30

 
       

Algorytm Floyda-Warshalla służy do wyznaczenia minimalnych kosztów dojścia pomiędzy każdą parą wierzchołków grafu skierowanego, nie posiadającego cykli o ujemnych kosztach, jest algorytmem programowania dynamicznego.

U podstaw alorytmu leżą dwie obserwacje. Pierwsza prosta, mówiąca o tym, że jeśli wierzchołek v jest osiągalny z wierzchołka u, to na ścieżce u-...-v o najmniejszym koszcie nie występuje cykl. Gdyby tak było, to usunięcie cyklu ze ścieżki dałoby ścieżkę tańszą lub ścieżkę o tym samym koszcie, gdy koszt cyklu wynosi zero.

Obserwacja druga jest nieco bardziej skomplikowana.
Niech wstępem do tej obserwacji będzie podział ścieżki o najmniejszym koszcie. Jeśli najtańszą ścieżkę u-...-i-...-v podzielimy na dwie u-...-i oraz i-...-v, to obie otrzymane ścieżki są ścieżkami o najmnieszym koszcie. Ale niestety nie w drugą stronę: jeśli ścieżki u-...-i oraz i-...-v, są ścieżkami o minimalnych kosztach, to ścieżka u-...-i-...-v wcale nie musi być najtańsza (trójkąt równoboczny o wszystkich krawędziach 1).
Metodą postępowania programowania dynamicznego można jednak sprawić, że owo twierdzenie odwrotne nabierze prawdziwości.

Załóżmy, że graf zawiera następującą ścieżkę 2-4-6-5-1-3 o najmniejszym koszcie. Wierzchołkami węwnętrznymi tej ścieżki są wierzchołki 1, 4, 5 i 6 - wybierzmy największy z nich, czyli 6. Teraz rozbijamy tą ściężkę na dwie względem wierzchołka 6, otrzymamy dwie ścieżki: 2-4-6 oraz 6-5-1-3. Co jest istotne, to obserwacja, że na każdej z tych ścieżek wierzchołki wewnętrzne są mniejsze od 6. Gdybyśmy znali minimalne koszty dościa pomiędzy każdą parą wierzchołków po wszystkich możliwych takich ścieżkach, że ich wierzchołki wewnętrzne pochodzą ze zbioru {1, 2, 3, 4, 5}, to sumując koszty obu ścieżek otrzymalibyśmy minimalny koszt całej ścieżki 2-4-6-5-1-3.

To przykład bardzo tendencyjny, bo 6 rozbija ścieżke na dwie. Gdyby najtańszą ścieżką była ścieżka 2-6-4-5-1-3, to otrzymalibyśmy ją z sumy kosztu krawędzi (2, 6) i kosztu najtańszej ścieżki 6-...-3.

Algorytm Floyda-Warshalla pracuje na tablicy D wymiaru n x n, w której na początku wpisujemy koszty wszystkich krawędzi lub wartość nieskończoności dla par wierzchołków nie połączonych krawędziami - na przekątnej tablicy wpisujemy wartości 0. Można powiedzieć, że początkowo tablica zawiera koszty wszystkich możliwych ścieżek, których wierzchołki wewnętrzne należą do zbioru pustego - są to bowiem ścieżki nie zawierające wierzchołków wewnętrznych.

Następnie do zbioru dozwolonych wierzchołków wewnętrznych dokładamy wierzchołek 1. Musimy tak przeształcić tablicę D, aby dla każdej pary wierzchołków u i v zawierała mniejszą z wartości: albo koszt krawędzi (u, v) albo koszt ścieżki u-1-v, czyli sumę kosztów dwóch krawędzi (u, 1) i (1, v).

For i:=1 To n Do
  For j:=1 To n Do
    If D[i, 1]+D[1, j]<D[i, j] Then D[i, j]:=D[i, 1]+D[1, j];

Teraz tablica D dla każdej pary wierzchołków zawiera minimalny koszt ścieżki pomiędzy nimi, po ścieżkach, których wierzchołki wewnętrzne należą do zbioru {1}.

Do zbioru dozwolonych wierzchołków wewnętrznych dokładamy wierzchołek 2:

For i:=1 To n Do
  For j:=1 To n Do
    If D[i, 2]+D[2, j]<D[i, j] Then D[i, j]:=D[i, 2]+D[2, j];

Teraz tablica D dla każdej pary wierzchołków zawiera minimalny koszt ścieżki pomiędzy nimi, po ścieżkach, których wierzchołki wewnętrzne należą do zbioru {1, 2}.

I tak kolejno wszystkie wierzchołki grafu, co ogólnie można zapisać dodatkową pętlą For:

For k:=1 To n Do
  For i:=1 To n Do
    For j:=1 To n Do
      If D[i, k]+D[k, j]<D[i, j] Then D[i, j]:=D[i, k]+D[k, j];

Złożoność obliczeniowa: O(n3).