Serwis Edukacyjny w I-LO w Tarnowie ![]() Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2023 mgr Jerzy Wałaszek |
ProblemW spójnym grafie ważonym należy znaleźć wagi najkrótszych ścieżek pomiędzy wszystkimi parami wierzchołków. |
Zadanie to rozwiązuje algorytm Floyda-Warshalla. Działa on w sposób dynamiczny i opiera się na spostrzeżeniu, że jeśli koszt dojścia z wierzchołka v do u jest większy od sumy kosztów dojść z wierzchołka v do k i z k do u, to za lepszy koszt należy przyjąć tę nową, mniejszą wartość.
Przetwarzany graf może posiadać krawędzie o wagach ujemnych, jednakże nie mogą w nim występować cykle ujemne (ang. negative cycles – cykle, w których suma wag krawędzi jest ujemna ). Algorytm Floyda-Warshalla może takie cykle wykrywać.
Algorytm w podstawowej wersji tworzy macierz d o rozmiarze n × n. Element d [ i, j ] tej macierzy będzie oznaczał najniższy koszt dojścia od wierzchołka i-tego do j-tego. Po utworzeniu macierzy algorytm wypełniana ją największymi wartościami dodatnimi (plus nieskończoność ). Następnie elementy d [ i, i ], dla i = 0, 1, ..., n - 1 ustawia na 0. Oznacza to, że koszt dojścia z wierzchołka i-tego do niego samego jest zerowy. Teraz dla każdego wierzchołka grafu k i każdej pary wierzchołków i, j badamy, czy koszt dojścia d [ i, j ] jest większy od sumy kosztów dojść d [ i, k ] = d [ k, j ]. Jeśli tak, to za koszt dojścia d [ i, j ] przyjmujemy wartość tej sumy ( oznacza to, że znaleźliśmy tańsze dojście od wierzchołka i-tego do j-tego poprzez wierzchołek k-ty – zwróć uwagę, że nie oznacza to wcale, że wierzchołki i oraz j muszą łączyć się pojedynczą krawędzią z wierzchołkiem k, po prostu d [ i, k ] jest minimalnym kosztem ścieżki od i do k, podobnie koszt d [ k, j ] jest minimalnym kosztem ścieżki od k do j, a koszty te algorytm wyznaczył wcześniej i teraz z nich korzysta – zasada programowania dynamicznego! ). Operacja ta wymaga trzech zagnieżdżonych pętli dla k, i, j. Z tego powodu algorytm Floyda-Warshalla ma klasę złożoności obliczeniowej równą O ( n 3 ), gdzie n oznacza liczbę wierzchołków w grafie. Złożoność pamięciowa wynosi O ( n 2 ).Prześledźmy na prostym przykładzie działanie tego algorytmu.
![]() |
|
Oto nasz graf ważony z ujemnymi wagami krawędzi. Przygotowujemy macierz d. Na głównej przekątnej umieszczamy 0, a w pozostałych komórkach umieszczamy ∞. | ||||||||||||||||||||||||||||||||||||
![]() |
|
Następnie dla każdej krawędzi u–v grafu w komórce d [ u, v ] umieszczamy wagę krawędzi w ( u–v ). Wartość d [ i, j ] = ∞ oznacza, że wierzchołek i-ty nie łączy się krawędzią z wierzchołkiem j-tym ( ale, jak zobaczymy dalej, może istnieć ścieżka łącząca te wierzchołki, a wtedy algorytm wprowadzi do d [ i, j ] jej koszt ). | ||||||||||||||||||||||||||||||||||||
![]() |
|
Rozpoczynamy przeglądanie kolejnych wierzchołków grafu od
wierzchołka k = 0. Dla każdej pary wierzchołków u, v sprawdzamy, czy zachodzi nierówność: d [ u, v ] > d [ u, k ] + d [ k, v ]. Jeśli tak, to d [ u, v ] ← d [ u, k ] + d [ k, v ]. W tym przypadku nierówność będzie spełniona dla par wierzchołków: ( 1, 3 ): d [ 1, 3 ] = ∞ > d [ 1, 0 ] + d [ 0, 3 ] = -4 + 8 = 4 ( 3, 2 ): d [ 3, 2 ] = ∞ > d [ 3, 0 ] + d [ 0, 2 ] = -1 + 4 = 3 Zmieniamy dla nich wpisy w macierzy d: d [ 1, 3 ] ← 4 d [ 3, 2 ] ← 3 |
||||||||||||||||||||||||||||||||||||
![]() |
|
Idziemy do następnego wierzchołka grafu, k = 1.
Znów sprawdzamy podaną wyżej nierówność dla wszystkich par
wierzchołków w grafie. Będzie spełniona dla p: ( 0, 2 ): d
[ 0, 2 ] = 4 > d
[ 0, 1 ] +
d [ 1, 2 ] = 5 + -2 = 3 |
||||||||||||||||||||||||||||||||||||
![]() |
|
Następny wierzchołek, k = 2. Nierówność jest
spełniona dla następujących par wierzchołków: ( 0, 4 ): d [ 0, 4 ] = 10 > d [ 0, 2 ] + d [ 2, 4 ] = 3 + 2 = 5 ( 1, 3 ): d [ 1, 3 ] = 4 > d [ 1, 2 ] + d [ 2, 3 ] = -2 + 5 = 3 ( 1, 4 ): d [ 1, 4 ] = 5 > d [ 1, 2 ] + d [ 2, 4 ] = -2 + 2 = 0 Ustawiamy: d [ 0, 4 ] ← 5 d [ 1, 3 ] ← 3 d [ 1, 4 ] ← 0 |
||||||||||||||||||||||||||||||||||||
![]() |
|
Następny wierzchołek, k = 3. ( 2, 0 ): d [ 2, 0 ] = ∞ > d [ 2, 3 ] + d [ 3, 0 ] = 5 + -2 = 3 ( 2, 1 ): d [ 2, 1 ] = ∞ > d [ 2, 3 ] + d [ 3, 1 ] = 5 + 2 = 7 ( 4, 0 ): d [ 4, 0 ] = ∞ > d [ 4, 3 ] + d [ 3, 0 ] = 2 + -2 = 0 ( 4, 1 ): d [ 4, 1 ] = ∞ > d [ 4, 3 ] + d [ 3, 1 ] = 2 + 2 = 4 ( 4, 2 ): d [ 4, 2 ] = 4 > d [ 4, 3 ] + d [ 3, 2 ] = 2 + 0 = 2 Ustawiamy: d [ 2, 0 ] ← 3 d [ 2, 1 ] ← 7 d [ 4, 0 ] ← 0 d [ 4, 1 ] ← 4 d [ 4, 2 ] ← 2 |
||||||||||||||||||||||||||||||||||||
![]() |
|
Ostatni wierzchołek, k = 4. ( 0, 3 ): d [ 0, 3 ] = 8 > d [ 0, 4 ] + d [ 4, 3 ] = 5 + 2 = 7 ( 1, 3 ): d [ 1, 3 ] = 3 > d [ 1, 4 ] + d [ 4, 3 ] = 0 + 2 = 2 ( 2, 0 ): d [ 2, 0 ] = 3 > d [ 2, 4 ] + d [ 4, 0 ] = 2 + 0 = 2 ( 2, 1 ): d [ 2, 1 ] = 7 > d [ 2, 4 ] + d [ 4, 1 ] = 2 + 4 = 6 ( 2, 3 ): d [ 2, 3 ] = 5 > d [ 2, 4 ] + d [ 4, 3 ] = 2 + 2 = 4 Ustawiamy: d [ 0, 3 ] ← 7 d [ 1, 3 ] ← 2 d [ 2, 0 ] ← 2 d [ 2, 1 ] ← 6 d [ 2, 3 ] ← 4 |
Koszty dojść są następujące:
d [ 0, 0 ] = 0 d [ 0, 1 ] = 5 d [ 0, 2 ] = 3 d [ 0, 3 ] = 7 d [ 0, 4 ] = 5 d [ 1, 0 ] = -4 d [ 1, 1 ] = 0 d [ 1, 2 ] = -2 d [ 1, 3 ] = 2 d [ 1, 4 ] = 0 d [ 2, 0 ] = 2 d [ 2, 1 ] = 6 d [ 2, 2 ] = 0 d [ 2, 3 ] = 4 d [ 2, 4 ] = 2 d [ 3, 0 ] = -2 d [ 3, 1 ] = 2 d [ 3, 2 ] = 0 d [ 3, 3 ] = 0 d [ 3, 4 ] = -1 d [ 4, 0 ] = 0 d [ 4, 1 ] = 4 d [ 4, 2 ] = 2 d [ 4, 3 ] = 2 d [ 4, 4 ] = 0 |
n | – | liczba wierzchołków w grafie, n ∈ C. |
graf | – | zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje. |
d | – | n × n elementowa macierz kosztów dojścia. Element d [ i, j ] oznacza minimalny koszt dojścia z wierzchołka i-tego do j-tego. |
k, i, j | – | numery wierzchołków w grafie, k, i, j ∈ C. |
K01: | Utwórz macierz d o rozmiarze n × n |
|
K02: | Dla i = 0, 1, ...,
n - 1: wykonuj kroki K03...K05 |
|
K03: | Dla j
= 0, 1, ..., n - 1: wykonuj: d [ i, j ] ← ∞ |
ustawiamy wszystkie komórki na nieskończoność |
K04: | d [ i, i ] ← 0 | elementy głównej przekątnej zerujemy |
K05: | Dla każdego
sąsiada j wierzchołka i : wykonuj: d [ i, j ] ← waga krawędzi i–j |
ustawiamy w d wagi krawędzi |
K06: | Dla k = 0, 1, ...,
n - 1, wykonuj kroki K07...K09 |
przechodzimy przez wszystkie wierzchołki grafu |
K07: | Dla i
= 0, 1, ..., n - 1, wykonuj kroki K08...K09 |
wybieramy wszystkie pary i, j wierzchołków w grafie |
K08: |
Dla j = 0, 1, ..., n - 1, wykonuj kroki K09 |
|
K09: |
Jeśli d [ i, j ] > d [ i,
k ] + d [ k, j ], to: d [ i, j ] ← d [ i, k ] + d [ k, j ] |
testujemy nierówność i, jeśli jest spełniona, modyfikujemy koszt |
K10: | Zakończ z wynikiem d |
Uwaga:
Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich. |
Poniższy program najniższe koszty
dojścia dla wszystkich par wierzchołków w grafie za pomocą algorytmu
Floyda-Warshalla. Definicja danych wejściowych jest następująca: W pierwszym wierszu program odczytuje kolejno liczbę wierzchołków n oraz liczbę krawędzi m. W m kolejnych wierszach znajdują się definicje krawędzi. Definicja składa się z trzech liczb x y w. Pierwsza liczba x oznacza początek krawędzi, druga liczba y oznacza koniec krawędzi, a trzecia liczba w jest wagą tej krawędzi. Na wyjściu program wypisuje koszt najkrótszej ścieżki pomiędzy każdymi dwoma wierzchołkami grafu. Jeśli ścieżka nie istnieje, pojawia się napis "NO PATH". |
Dane przykładowe (przekopiuj do
schowka i wklej do okna konsoli ):
|
Pascal// Algorytm Floyda-Warshalla // Data : 20.04.2014 // (C)2014 mgr Jerzy Wałaszek //--------------------------- program floyd_warshall; // Typ danych dla macierzy dynamicznej type nptr = array of integer; var d : array of nptr; // Macierz minimalnych kosztów dojścia i, j, k, n, m, x, y, w : integer; begin read ( n, m ); // Czytamy liczbę wierzchołków oraz krawędzi SetLength ( d, n ); // Tworzymy dynamiczną macierz d for i := 0 to n - 1 do begin SetLength ( d [ i ], n ); // Tworzymy wiersz macierzy for j := 0 to n - 1 do d [ i ][ j ] := MAXINT; // Wiersz wypełniamy największą liczbą dodatnią d [ i ][ i ] := 0; // Jednakże na przekątnej wpisujemy 0 end; for i := 1 to m do begin read ( x, y, w ); // Czytamy definicję krawędzi d [ x ][ y ] := w; // Wagę krawędzi umieszczamy w macierzy d end; // Algorytm Floyda-Warshalla for k := 0 to n - 1 do for i := 0 to n - 1 do for j := 0 to n - 1 do begin if( d [ i ][ k ] = MAXINT ) or ( d [ k ][ j ] = MAXINT ) then continue; w := d [ i ][ k ] + d [ k ][ j ]; if d [ i ][ j ] > w then d [ i ][ j ] := w; end; // Wyświetlamy wyniki writeln; for i := 0 to n - 1 do for j := 0 to n - 1 do begin write ( 'd [ ', i, ', ', j, ' ] = ' if d [ i ][ j ] = MAXINT then writeln ( 'NO PATH' ) else writeln ( d [ i ][ j ] ); end; // Usuwamy macierz dynamiczną for i := 0 to n - 1 do SetLength ( d [ i ], 0 ); SetLength ( d, 0 ); end. |
C++// Algorytm Floyda-Warshalla // Data : 20.04.2014 // (C)2014 mgr Jerzy Wałaszek //--------------------------- #include <iostream> using namespace std; const int MAXINT = 2147483647; // "plus nieskończoność" int main( ) { int ** d; // Macierz minimalnych kosztów dojścia int i, j, k, n, m, x, y, w; cin >> n >> m; // Czytamy liczbę wierzchołków oraz krawędzi d = new int * [ n ]; // Tworzymy dynamiczną macierz d for( i = 0; i < n; i++ ) { d [ i ] = new int [ n ]; // Tworzymy wiersz macierzy for( j = 0; j < n; j++ ) d [ i ][ j ] = MAXINT; // Wiersz wypełniamy największą liczbą dodatnią d [ i ][ i ] = 0; // Jednakże na przekątnej wpisujemy 0 } for( i = 0; i < m; i++ ) { cin >> x >> y >> w; // Czytamy definicję krawędzi d [ x ][ y ] = w; // Wagę krawędzi umieszczamy w macierzy d } // Algorytm Floyda-Warshalla for( k = 0; k < n; k++ ) for( i = 0; i < n; i++ ) for( j = 0; j < n; j++ ) { if( ( d [ i ][ k ] == MAXINT ) || ( d [ k ][ j ] == MAXINT ) ) continue; w = d [ i ][ k ] + d [ k ][ j ]; if( d [ i ][ j ] > w ) d [ i ][ j ] = w; } // Wyświetlamy wyniki cout << endl; for( i = 0; i < n; i++ ) for( j = 0; j < n; j++ ) { cout << "d [ " << i << ", " << j << " ] = "; if( d [ i ][ j ] == MAXINT ) cout << "NO PATH"; else cout << d [ i ][ j ]; cout << endl; } // Usuwamy macierz dynamiczną for( i = 0; i < n; i++ ) delete [ ] d [ i ]; delete [ ] d; return 0; } |
Basic' Algorytm Floyda-Warshalla ' Data : 20.04.2014 ' (C)2014 mgr Jerzy Wałaszek '--------------------------- const MAXINT = 2147483647 ' "plus nieskończoność" Dim As Integer Ptr Ptr d ' Macierz minimalnych kosztów dojścia Dim As Integer i, j, k, n, m, x, y, w Open Cons For Input As #1 Input #1, n, m ' Czytamy liczbę wierzchołków oraz krawędzi d = New Integer Ptr [ n ] ' Tworzymy dynamiczną macierz d For i = 0 To n - 1 d [ i ] = New Integer [ n ] ' Tworzymy wiersz macierzy For j = 0 To n - 1 d [ i ][ j ] = MAXINT ' Wiersz wypełniamy największą liczbą dodatnią Next d [ i ][ i ] = 0 ' Jednakże na przekątnej wpisujemy 0 Next For i = 1 To m Input #1, x, y, w ' Czytamy definicję krawędzi d [ x ][ y ] = w ' Wagę krawędzi umieszczamy w macierzy d Next Close #1 ' Algorytm Floyda-Warshalla For k = 0 To n - 1 For i = 0 To n - 1 For j = 0 To n - 1 if( d [ i ][ k ] = MAXINT ) OrElse ( d [ k ][ j ] = MAXINT ) Then Continue For w = d [ i ][ k ] + d [ k ][ j ] If d [ i ][ j ] > w Then d [ i ][ j ] = w Next Next Next ' Wyświetlamy wyniki Print For i = 0 To n - 1 For j = 0 To n - 1 Print Using "d [ &, & ] =";i;j; If d [ i ][ j ] = MAXINT Then Print " NO PATH" Else Print d [ i ][ j ] End If Next Next ' Usuwamy macierz dynamiczną For i = 0 To n - 1 Delete [ ] d [ i ] Next Delete [ ] d End |
Wynik: |
5 13 0 1 5 0 2 4 0 3 8 1 0 -4 1 2 -2 1 4 5 2 3 5 2 4 2 3 0 -1 3 1 2 3 4 -1 4 2 4 4 3 2 d [ 0, 0 ] = 0 d [ 0, 1 ] = 5 d [ 0, 2 ] = 3 d [ 0, 3 ] = 7 d [ 0, 4 ] = 5 d [ 1, 0 ] = -4 d [ 1, 1 ] = 0 d [ 1, 2 ] = -2 d [ 1, 3 ] = 2 d [ 1, 4 ] = 0 d [ 2, 0 ] = 2 d [ 2, 1 ] = 6 d [ 2, 2 ] = 0 d [ 2, 3 ] = 4 d [ 2, 4 ] = 2 d [ 3, 0 ] = -2 d [ 3, 1 ] = 2 d [ 3, 2 ] = 0 d [ 3, 3 ] = 0 d [ 3, 4 ] = -1 d [ 4, 0 ] = 0 d [ 4, 1 ] = 4 d [ 4, 2 ] = 2 d [ 4, 3 ] = 2 d [ 4, 4 ] = 0 |
Podstawowy algorytm Floyda-Warshalla oblicza jedynie minimalne koszty ścieżek pomiędzy wszystkimi parami wierzchołków w grafie ważonym. Nie dostajemy jednakże informacji o samych ścieżkach. Przez prostą modyfikację algorytmu możemy również otrzymać te najkrótsze ścieżki. Najpierw jednak pokażemy, jak rozpoznać w grafie cykl ujemny. Otóż w tym celu wystarczy po zakończeniu działania algorytmu sprawdzić główną przekątną macierzy d. Jeśli jakikolwiek wyraz na głównej przekątnej będzie ujemny, to w grafie mamy cykl ujemny. Wyjaśnienie tego faktu jest proste. Koszt dojścia wierzchołka do siebie samego jest ustawiany na początku algorytmu na zero. Koszt każdego cyklu dodatniego jest większy od zera, zatem przejście przez cykl dodatni i powrót do wierzchołka ma koszt większy od zera i wartość ta nie będzie zmieniona. Jeśli jednak wierzchołek należy do cyklu ujemnego, to przejście przez ten cykl i powrót do wierzchołka daje wartość ujemną, którą zostanie zastąpione to zero. Jeśli graf zawiera cykl ujemny, to nie można w nim wyznaczyć wszystkich najkrótszych ścieżek (każda ścieżka mająca dostęp do takiego cyklu może stać się najkrótszą przez kilkakrotne przejście przez cykl ujemny ). Dlatego po rozpoznaniu cyklu ujemnego algorytm powinien zgłosić błąd (np. jeśli realizujemy go w postaci funkcji, to zwraca true, gdy wszystko jest OK, a false, gdy napotka cykl ujemny ).
Do zapamiętania ścieżek potrzebujemy dodatkowej macierzy poprzedników p o rozmiarze n × n. W macierzy p element p [ u, v ] będzie oznaczał poprzednika wierzchołka v na najkrótszej ścieżce. Na początku algorytmu macierz p wypełniamy wartością -1, która oznacza brak poprzednika. Następnie dla każdej krawędzi u–v grafu w elemencie p [ u, v ] umieszczamy u. Teraz w trakcie działania algorytmu Floyda-Warshala w momencie modyfikacji macierzy d modyfikujemy również macierz p. Otóż, gdy spełniona jest nierówność:
d [ i, j ] > d [ i, k ] + d [ k, j ] |
i do macierzy d wprowadzamy:
d [ i, j ] ← d [ i, k ] + d [ k, j ] |
to wierzchołek k-ty staje się wierzchołkiem pośrednim na najkrótszej ścieżce łączącej wierzchołek i-ty z wierzchołkiem j-tym. Z tego powodu jest on również poprzednikiem wierzchołka j-tego na tej ścieżce. Dlatego w tablicy p umieszczamy wpis:
p [ i, j ] ← p [ k, j ] |
Wpis ten oznacza poprzednik wierzchołka j-tego na ścieżce wiodącej do wierzchołka k-tego, którego poprzednikiem jest z kolei wierzchołek i-ty.
Odtworzenie poprawnej ścieżki wymaga dodatkowych działań. Po zakończeniu pracy algorytmu Floyda-Warshala najkrótszą ścieżkę pomiędzy wierzchołkami i-tym i j-tym znajdziemy następująco:
Rekurencyjnie szukamy ścieżki od wierzchołka i-tego do j-tego. Najpierw sprawdzamy, czy zachodzi równość i = j. Jeśli tak, to kończymy przez wypisanie i, ponieważ gdy j jest równe i, to jego poprzednikiem jest zawsze i. Następnie sprawdzamy, czy p [ i, j ] = -1. Jeśli tak, to przerywamy tworzenie ścieżki, ponieważ ona nie istnieje z powodu braku poprzednika. Na koniec, jeśli dwa pierwsze warunki nie będą spełnione, to rekurencyjnie wywołujemy ten sam algorytm dla i oraz p [ i, j ]. Spowoduje to znalezienie i wypisanie wszystkich kolejnych poprzedników węzła j-tego. Na koniec wypisujemy węzeł j-ty i ścieżka staje się kompletna.
Prześledźmy działanie zmodyfikowanego algorytmu Floyda-Warshala w poniższej tabeli:
![]() |
|
|
Oto nasz graf ważony z ujemnymi wagami krawędzi. Przygotowujemy macierz kosztów dojścia d. Na głównej przekątnej umieszczamy 0, a w pozostałych komórkach umieszczamy ∞. Następnie przygotowujemy macierz poprzedników p. Wszystkie jej komórki wstępnie ustawiamy na -1. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
|
|
Następnie dla każdej krawędzi u–v grafu w komórce d [ u, v ] umieszczamy wagę krawędzi w ( u–v ). Wartość d [ i, j ] = ∞ oznacza, że wierzchołek i-ty nie łączy się krawędzią z wierzchołkiem j-tym ( ale, jak zobaczymy dalej, może istnieć ścieżka łącząca te wierzchołki, a wtedy algorytm wprowadzi do d [ i, j ] jej koszt ). Również modyfikujemy macierz p, umieszczając w p [ u, v ] wartość u. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
|
|
Rozpoczynamy przeglądanie kolejnych wierzchołków grafu od
wierzchołka k = 0. Dla każdej pary wierzchołków u, v sprawdzamy, czy zachodzi nierówność: d [ u, v ] > d [ u, k ] = d [ k, v ]. Jeśli tak, to d [ u, v ] ← d [ u, k ] + d [ k, v ]. W tym przypadku nierówność będzie spełniona dla par wierzchołków: ( 1, 3 ): d [ 1, 3 ] = ∞ > d [ 1, 0 ] + d [ 0, 3 ] = -4 + 8 = 4 ( 3, 2 ): d [ 3, 2 ] = ∞ > d [ 3, 0 ] + d [ 0, 2 ] = -1 + 4 = 3 Zmieniamy dla nich wpisy w macierzach d i p: d [ 1, 3 ] ← 4, p [ 1, 3 ] ← p [ 0, 3 ] = 0 d [ 3, 2 ] ← 3, p [ 3, 2 ] ← p [ 0, 2 ] = 0 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
|
|
Idziemy do następnego wierzchołka grafu, k = 1.
Znów sprawdzamy podaną wyżej nierówność dla wszystkich par
wierzchołków w grafie. Będzie spełniona dla par: ( 0, 2 ): d [ 0, 2 ] = 4 > d [ 0, 1 ] + d [ 1, 2 ] = 5 + -2 = 3 ( 0, 4 ): d [ 0, 4 ] = ∞ > d [ 0, 1 ] + d [ 1, 4 ] = 5 + 5 = 10 ( 3, 0 ): d [ 3, 0 ] = -1 > d [ 3, 1 ] + d [ 1, 0 ] = 2 + -4 = -2 ( 3, 2 ): d [ 3, 2 ] = 3 > d [ 3, 1 ] + d [ 1, 2 ] = 2 + -2 = 0 Ustawiamy: d [ 0, 2 ] ← 3, p [ 0, 2 ] ← p [ 1, 2 ] = 1 d [ 0, 4 ] ← 10, p [ 0, 4 ] ← p [ 1, 4 ] = 1 d [ 3, 0 ] ← -2, p [ 3, 0 ] ← p [ 1, 0 ] = 1 d [ 3, 2 ] ← 0, p [ 3, 2 ] ← p [ 3, 2 ] = 1 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
|
|
Następny wierzchołek, k = 2. Nierówność jest
spełniona dla następujących par wierzchołków: ( 0, 4 ): d [ 0, 4 ] = 10 > d [ 0, 2 ] + d [ 2, 4 ] = 3 + 2 = 5 ( 1, 3 ): d [ 1, 3 ] = 4 > d [ 1, 2 ] + d [ 2, 3 ] = -2 + 5 = 3 ( 1, 4 ): d [ 1, 4 ] = 5 > d [ 1, 2 ] + d [ 2, 4 ] = -2 + 2 = 0 Ustawiamy: d [ 0, 4 ] ← 5, p [ 0, 4 ] ← p [ 2, 4 ] = 2 d [ 1, 3 ] ← 3, p [ 1, 3 ] ← p [ 2, 3 ] = 2 d [ 1, 4 ] ← 0, p [ 1, 4 ] ← p [ 1, 4 ] = 2 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
|
|
Następny wierzchołek, k = 3. ( 2, 0 ): d [ 2, 0 ] = ∞ > d [ 2, 3 ] + d [ 3, 0 ] = 5 + -2 = 3 ( 2, 1 ): d [ 2, 1 ] = ∞ > d [ 2, 3 ] + d [ 3, 1 ] = 5 + 2 = 7 ( 4, 0 ): d [ 4, 0 ] = ∞ > d [ 4, 3 ] + d [ 3, 0 ] = 2 + -2 = 0 ( 4, 1 ): d [ 4, 1 ] = ∞ > d [ 4, 3 ] + d [ 3, 1 ] = 2 + 2 = 4 ( 4, 2 ): d [ 4, 2 ] = 4 > d [ 4, 3 ] + d [ 3, 2 ] = 2 + 0 = 2 Ustawiamy: d [ 2, 0 ] ← 3, p [ 2, 0 ] ← p [ 3, 0 ] = 1 d [ 2, 1 ] ← 7, p [ 2, 1 ] ← p [ 3, 1 ] = 3 d [ 4, 0 ] ← 0, p [ 4, 0 ] ← p [ 3, 0 ] = 1 d [ 4, 1 ] ← 4, p [ 4, 1 ] ← p [ 3, 1 ] = 3 d [ 4, 2 ] ← 2, p [ 4, 2 ] ← p [ 3, 2 ] = 1 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
|
|
Ostatni wierzchołek, k = 4. ( 0, 3 ): d [ 0, 3 ] = 8 > d [ 0, 4 ] + d [ 4, 3 ] = 5 + 2 = 7 ( 1, 3 ): d [ 1, 3 ] = 3 > d [ 1, 4 ] + d [ 4, 3 ] = 0 + 2 = 2 ( 2, 0 ): d [ 2, 0 ] = 3 > d [ 2, 4 ] + d [ 4, 0 ] = 2 + 0 = 2 ( 2, 1 ): d [ 2, 1 ] = 7 > d [ 2, 4 ] + d [ 4, 1 ] = 2 + 4 = 6 ( 2, 3 ): d [ 2, 3 ] = 5 > d [ 2, 4 ] + d [ 4, 3 ] = 2 + 2 = 4 Ustawiamy: d [ 0, 3 ] ← 7, p [ 0, 3 ] ← p [ 4, 3 ] = 4 d [ 1, 3 ] ← 2, p [ 1, 3 ] ← p [ 4, 3 ] = 4 d [ 2, 0 ] ← 2, p [ 2, 0 ] ← p [ 4, 0 ] = 1 d [ 2, 1 ] ← 6, p [ 2, 1 ] ← p [ 4, 1 ] = 3 d [ 2, 3 ] ← 4, p [ 2, 3 ] ← p [ 4, 3 ] = 4 |
Teraz pokażemy, jak wydobyć rekurencyjnie z macierzy p informację o najkrótszej ścieżce. Załóżmy, że chcemy odczytać najkrótszą ścieżkę od wierzchołka 4 do 2:
![]() |
|
Poziom rekurencji 0: i = 4, j = 2 Ponieważ i nie jest równe j oraz p [ 4, 2 ] jest różne od -1, to wywołujemy rekurencyjnie ten sam algorytm z parametrami: i = 4, j = p [ 4, 2 ] = 1. Powrót nastąpi w to miejsce, gdzie wypiszemy j i zakończymy algorytm. |
||||||||||||||||||||||||||||||||||||
![]() |
|
Poziom rekurencji 1: i = 4, j = 1 Wywołujemy rekurencyjnie ten sam algorytm z parametrami: i = 4, j = p [ 4, 1 ] = 3. |
||||||||||||||||||||||||||||||||||||
![]() |
|
Poziom rekurencji 2: i = 4, j = 3 Wywołujemy rekurencyjnie ten sam algorytm z parametrami: i = 4, j = p [ 4, 3 ] = 4. |
||||||||||||||||||||||||||||||||||||
![]() |
|
Poziom rekurencji 3: i = 4, j = 4 Zachodzi równość i = j. Wypisujemy 4 i wracamy na poziom 2. |
||||||||||||||||||||||||||||||||||||
![]() |
Wy: 4 3 | Poziom rekurencji 2: i = 4, j = 3 Po powrocie z wywołania rekurencyjnego na poziomie 3 wypisujemy j i wracamy na poziom 1. |
||||||||||||||||||||||||||||||||||||
![]() |
Wy: 4 3 1 | Poziom rekurencji 1: i = 4, j = 1 Po powrocie z wywołania rekurencyjnego na poziomie 2 wypisujemy j i wracamy na poziom 0. |
||||||||||||||||||||||||||||||||||||
![]() |
Wy: 4 3 1 2 | Poziom rekurencji 0: i = 4, j = 2 Po powrocie z wywołania rekurencyjnego na poziomie 1 wypisujemy j i kończymy algorytm. Ścieżka jest gotowa. |
n | – | liczba wierzchołków w grafie, n ∈ C. |
graf | – | zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje. |
true – poprawne zakończenie, wynikiem są zawartości dwóch macierzy:
d | – | n × n elementowa macierz kosztów dojścia. Element d [ i, j ] oznacza minimalny koszt dojścia z wierzchołka i-tego do j-tego. |
p | – | n × n elementowa macierz poprzedników. Element p [ i, j ] oznacza poprzednik wierzchołka j-tego na minimalnej ścieżce od wierzchołka i-tego do j-tego. |
false – graf zawiera cykl ujemny.
k, i, j | – | numery wierzchołków w grafie, k, i, j ∈ C. |
K01: | Utwórz macierze d i p o rozmiarze n × n |
|
K02: | Dla i = 0, 1, ...,
n
- 1: wykonuj kroki K03...K05 |
|
K03: | Dla j
= 0, 1, ..., n - 1, wykonuj: d [ i, j ] ← ∞ p [ i, j ] ← -1 |
ustawiamy wszystkie komórki d na nieskończoność, a wszystkie komórki p na -1 |
K04: | d [ i, i ] ← 0 | elementy głównej przekątnej zerujemy |
K05: | Dla każdego
sąsiada j wierzchołka i : wykonuj: d [ i, j ] ← waga krawędzi i–j p [ i, j ] ← i |
ustawiamy w d wagi krawędzi w p poprzedniki wierzchołków j-tych |
K06: | Dla k = 0, 1, ...,
n - 1, wykonuj kroki K07...K09 |
przechodzimy przez wszystkie wierzchołki grafu |
K07: | Dla i
= 0, 1, ..., n - 1, wykonuj kroki K08...K09 |
wybieramy wszystkie pary i, j wierzchołków w grafie |
K08: |
Dla j = 0, 1, ..., n - 1, wykonuj kroki K09 |
|
K09: |
Jeśli d [ i, j ] > d [ i,
k ] + d [ k, j ], to: d [ i, j ] ← d [ i, k ] + d [ k, j ] p [ i, j ] ← p [ k, j ] |
testujemy nierówność i, jeśli jest spełniona, modyfikujemy koszt. Jako poprzednik j na ścieżce od i do j ustawiamy poprzednik j na ścieżce od k do j. |
K10: | Dla i = 0, 1, ...,
n
- 1: wykonuj: Jeśli d [ i, i ] = -1, to zakończ z wynikiem false |
wykryto cykl ujemny |
K11: | Zakończ z wynikiem true |
p | – | n × n elementowa macierz poprzedników. Element p [ i, j ] oznacza poprzednik wierzchołka j-tego na minimalnej ścieżce od wierzchołka i-tego do j-tego. |
i | – | wierzchołek startowy krawędzi, i ∈ C. |
j | – | wierzchołek końcowy krawędzi, j ∈ C. |
minimalna ścieżka od wierzchołka i-tego do j-tego lub napis "NO PATH", jeśli taka ścieżka nie istnieje
K01: | Jeśli i = j, to pisz i i zakończ |
|
K02: | Jeśli p [ i, j
] = -1, to pisz "NO PATH" i zakończ |
|
K03: | FWPath ( p, i, p [ i, j ] ) | wywołanie rekurencyjne |
K04: | Pisz j | ostatni wierzchołek ścieżki |
K05: | Zakończ |
Uwaga:
Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich. |
Poniższy wyznacza ścieżki o
najniższym koszcie dojścia dla wszystkich par wierzchołków w grafie
za pomocą rozszerzonego algorytmu Floyda-Warshalla. Definicja danych
wejściowych jest następująca: W pierwszym wierszu program odczytuje kolejno liczbę wierzchołków n oraz liczbę krawędzi m. W m kolejnych wierszach znajdują się definicje krawędzi. Definicja składa się z trzech liczb x y w. Pierwsza liczba x oznacza początek krawędzi, druga liczba y oznacza koniec krawędzi, a trzecia liczba w jest wagą tej krawędzi. Na wyjściu dla każdej pary wierzchołków program wypisuje minimalną ścieżkę oraz jej koszt. Jeśli ścieżka nie istnieje, pojawia się napis "NO PATH". |
Dane przykładowe (przekopiuj do
schowka i wklej do okna konsoli ):
|
Pascal// Algorytm Floyda-Warshalla // Data : 21.04.2014 // (C)2014 mgr Jerzy Wałaszek //--------------------------- program floyd_warshall2; // Typ danych dla macierzy dynamicznej type nptr = array of integer; // Zmienne globalne var d, p : array of nptr; // Macierze kosztów oraz poprzedników n, m : integer; // Liczba wierzchołków i krawędzi // Funkcja wyznaczania kosztów dojścia oraz // minimalnych ścieżek w grafie ważonym //------------------------------------------ function FloydWarshall : boolean; var i, j, k, w : integer; begin for k := 0 to n - 1 do for i := 0 to n - 1 do for j := 0 to n - 1 do begin if( d [ i ][ k ] = MAXINT ) or ( d [ k ][ j ] = MAXINT ) then continue; w := d [ i ][ k ] = d [ k ][ j ]; if d [ i ][ j ] > w then begin d [ i ][ j ] := w; p [ i ][ j ] := p [ k ][ j ]; end; end; for i := 0 to n - 1 do if d [ i ][ i ] < 0 then Exit ( false ); // Ujemny cykl FloydWarshall := true; end; // Rekurencyjna procedura odtwarzania minimalnej // ścieżki z macierzy poprzedników p //---------------------------------------------- procedure FWPath ( i, j : integer ); begin if i = j then write ( i, ' ' ) else if p [ i ][ j ] = -1 then write ( 'NO PATH' ) else begin FWPath ( i, p [ i ][ j ] ); write ( j, ' ' ); end; end; // ********************** // *** PROGRAM GŁÓWNY *** // ********************** var i, j, x, y, w : integer; begin read ( n, m ); // Czytamy liczbę wierzchołków oraz krawędzi SetLength ( d, n ); // Tworzymy dynamiczną macierz d SetLength ( p, n ); // Tworzymy dynamiczną macierz p for i := 0 to n - 1 do begin SetLength ( d [ i ], n ); // Tworzymy wiersz macierzy d SetLength ( p [ i ], n ); // Tworzymy wiersz macierzy p for j := 0 to n - 1 do begin d [ i ][ j ] := MAXINT; // Wiersz d wypełniamy największą liczbą dodatnią p [ i ][ j ] := -1; // Wiersz p wypełniamy liczbami -1 ( brak poprzednika ) end; d [ i ][ i ] := 0; // Jednakże na przekątnej d wpisujemy 0 end; for i := 1 to m do begin read ( x, y, w ); // Czytamy definicję krawędzi d [ x ][ y ] := w; // Wagę krawędzi umieszczamy w macierzy d p [ x ][ y ] := x; // Poprzednikiem y jest x end; // Wywołujemy procedurę Floyda-Warshalla writeln; if FloydWarshall then begin // Wyświetlamy wyniki for i := 0 to n - 1 do for j := 0 to n - 1 do begin write ( i, '-', j, ' : ' ); FWPath ( i, j ); if d [ i ][ j ] < MAXINT then write ( '$', d [ i ][ j ] ); writeln; end; end else writeln ( 'Negative cycle found' ); writeln; // Usuwamy macierze dynamiczne for i := 0 to n - 1 do begin SetLength ( d [ i ], 0 ); SetLength ( p [ i ], 0 ); end; SetLength ( d, 0 ); SetLength ( p, 0 ); end. |
C++// Algorytm Floyda-Warshalla // Data : 21.04.2014 // (C)2014 mgr Jerzy Wałaszek //--------------------------- #include <iostream> using namespace std; const int MAXINT = 2147483647; // "plus nieskończoność" // Zmienne globalne int **d, **p; // Macierze kosztów oraz poprzedników int n, m; // Liczba wierzchołków i krawędzi // Funkcja wyznaczania kosztów dojścia oraz // minimalnych ścieżek w grafie ważonym //------------------------------------------ bool FloydWarshall( ) { int i, j, k, w; for( k = 0; k < n; k++ ) for( i = 0; i < n; i++ ) for( j = 0; j < n; j++ ) { if( ( d [ i ][ k ] == MAXINT ) || ( d [ k ][ j ] == MAXINT ) ) continue; w = d [ i ][ k ] + d [ k ][ j ]; if( d [ i ][ j ] > w ) { d [ i ][ j ] = w; p [ i ][ j ] = p [ k ][ j ]; } } for( i = 0; i < n; i++ ) if( d [ i ][ i ] < 0 ) return false; // Ujemny cykl return true; } // Rekurencyjna procedura odtwarzania minimalnej // ścieżki z macierzy poprzedników p //---------------------------------------------- void FWPath ( int i, int j ) { if( i == j ) cout << i << " "; else if( p [ i ][ j ] == -1 ) cout << "NO PATH"; else { FWPath ( i, p [ i ][ j ] ); cout << j << " "; } } // ********************** // *** PROGRAM GŁÓWNY *** // ********************** int main( ) { int i, j, x, y, w; cin >> n >> m; // Czytamy liczbę wierzchołków oraz krawędzi d = new int * [ n ]; // Tworzymy dynamiczną macierz d p = new int * [ n ]; // Tworzymy dynamiczną macierz p for( i = 0; i < n; i++ ) { d [ i ] = new int [ n ]; // Tworzymy wiersz macierzy d p [ i ] = new int [ n ]; // Tworzymy wiersz macierzy p for( j = 0; j < n; j++ ) { d [ i ][ j ] = MAXINT; // Wiersz d wypełniamy największą liczbą dodatnią p [ i ][ j ] = -1; // Wiersz p wypełniamy liczbami -1 ( brak poprzednika ) } d [ i ][ i ] = 0; // Jednakże na przekątnej d wpisujemy 0 } for( i = 0; i < m; i++ ) { cin >> x >> y >> w; // Czytamy definicję krawędzi d [ x ][ y ] = w; // Wagę krawędzi umieszczamy w macierzy d p [ x ][ y ] = x; // Poprzednikiem y jest x } // Wywołujemy procedurę Floyda-Warshalla cout << endl; if( FloydWarshall( ) ) { // Wyświetlamy wyniki for( i = 0; i < n; i++ ) for( j = 0; j < n; j++ ) { cout << i << "-" << j << ": "; FWPath ( i, j ); if( d [ i ][ j ] < MAXINT ) cout << "$" << d [ i ][ j ]; cout << endl; } } else cout << "Negative cycle found" << endl; cout << endl; // Usuwamy macierze dynamiczne for( i = 0; i < n; i++ ) { delete [ ] d [ i ]; delete [ ] p [ i ]; } delete [ ] d; delete [ ] p; return 0; } |
Basic' Algorytm Floyda-Warshalla ' Data : 21.04.2014 ' (C)2014 mgr Jerzy Wałaszek '--------------------------- const MAXINT = 2147483647 ' "plus nieskończoność" ' Zmienne globalne Dim Shared As Integer Ptr Ptr d, p ' Macierze kosztów oraz poprzedników Dim Shared As Integer n, m ' Liczba wierzchołków i krawędzi ' Funkcja wyznaczania kosztów dojścia oraz ' minimalnych ścieżek w grafie ważonym '------------------------------------------ Function FloydWarshall( ) As Integer Dim As Integer i, j, k, w For k = 0 To n - 1 For i = 0 To n - 1 For j = 0 To n - 1 if( d [ i ][ k ] = MAXINT ) OrElse ( d [ k ][ j ] = MAXINT ) Then Continue For w = d [ i ][ k ] + d [ k ][ j ] If d [ i ][ j ] > w Then d [ i ][ j ] = w p [ i ][ j ] = p [ k ][ j ] End If Next Next Next For i = 0 To n - 1 If d [ i ][ i ] < 0 then Return 0 ' Ujemny cykl Next Return 1 End Function ' Rekurencyjna procedura odtwarzania minimalnej ' ścieżki z macierzy poprzedników p '---------------------------------------------- Sub FWPath ( ByVal i As Integer, byval j As Integer ) If i = j Then Print i; ElseIf p [ i ][ j ] = -1 Then Print " NO PATH"; Else FWPath ( i, p [ i ][ j ] ) Print j; End If End Sub ' ********************** ' *** PROGRAM GŁÓWNY *** ' ********************** Dim As Integer i, j, x, y, w Open Cons For Input As #1 Input #1, n, m ' Czytamy liczbę wierzchołków oraz krawędzi d = New Integer Ptr [ n ] ' Tworzymy dynamiczną macierz d p = New Integer Ptr [ n ] ' Tworzymy dynamiczną macierz p For i = 0 To n - 1 d [ i ] = New Integer [ n ] ' Tworzymy wiersz macierzy d p [ i ] = New Integer [ n ] ' Tworzymy wiersz macierzy p For j = 0 To n - 1 d [ i ][ j ] = MAXINT ' Wiersz d wypełniamy największą liczbą dodatnią p [ i ][ j ] = -1 ' Wiersz p wypełniamy liczbami -1 ( brak poprzednika ) Next d [ i ][ i ] = 0 ' Jednakże na przekątnej d wpisujemy 0 Next For i = 1 To m Input #1, x, y, w ' Czytamy definicję krawędzi d [ x ][ y ] = w ' Wagę krawędzi umieszczamy w macierzy d p [ x ][ y ] = x ' Poprzednikiem y jest x Next ' Wywołujemy procedurę Floyda-Warshalla Print If FloydWarshall( ) = 1 Then ' Wyświetlamy wyniki For i = 0 To n - 1 For j = 0 To n - 1 Print Using "&-&:";i;j; FWPath ( i, j ) If d [ i ][ j ] < MAXINT Then Print Using " $&";d [ i ][ j ]; Print Next Next Else Print "Negative cycle found" End If Print ' Usuwamy macierze dynamiczne for i = 0 To n - 1 Delete [ ] d [ i ] Delete [ ] p [ i ] Next Delete [ ] d Delete [ ] p End |
Wynik: |
5 13 0 1 5 0 2 4 0 3 8 1 0 -4 1 2 -2 1 4 5 2 3 5 2 4 2 3 0 -1 3 1 2 3 4 -1 4 2 4 4 3 2 0-0 : 0 $0 0-1 : 0 1 $5 0-2 : 0 1 2 $3 0-3 : 0 1 2 4 3 $7 0-4 : 0 1 2 4 $5 1-0 : 1 0 $-4 1-1 : 1 $0 1-2 : 1 2 $-2 1-3 : 1 2 4 3 $2 1-4 : 1 2 4 $0 2-0 : 2 4 3 1 0 $2 2-1 : 2 4 3 1 $6 2-2 : 2 $0 2-3 : 2 4 3 $4 2-4 : 2 4 $2 3-0 : 3 1 0 $-2 3-1 : 3 1 $2 3-2 : 3 1 2 $0 3-3 : 3 $0 3-4 : 3 4 $-1 4-0 : 4 3 1 0 $0 4-1 : 4 3 1 $4 4-2 : 4 3 1 2 $2 4-3 : 4 3 $2 4-4 : 4 $0 |
![]() |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2023 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.