Algorytmy i Struktury Danych - Algorytm Floyda-Warshalla

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ść.

obrazek

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³ ), gdzie n oznacza liczbę wierzchołków w grafie. Złożoność pamięciowa wynosi O ( n² ).

Prześledźmy na prostym przykładzie działanie tego algorytmu.

d	0	1	2	3	4
0	0	∞	∞	∞	∞
1	∞	0	∞	∞	∞
2	∞	∞	0	∞	∞
3	∞	∞	∞	0	∞
4	∞	∞	∞	∞	0

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 ∞.

d	0	1	2	3	4
0	0	5	4	8	∞
1	-4	0	-2	∞	5
2	∞	∞	0	5	2
3	-1	2	∞	0	-1
4	∞	∞	4	2	0

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 ).

d	0	1	2	3	4
0	0	5	4	8	∞
1	-4	0	-2	4	5
2	∞	∞	0	5	2
3	-1	2	3	0	-1
4	∞	∞	4	2	0

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

d	0	1	2	3	4
0	0	5	3	8	10
1	-4	0	-2	4	5
2	∞	∞	0	5	2
3	-2	2	0	0	-1
4	∞	∞	4	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 p:

( 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
d [ 0, 4 ] ← 10
d [ 3, 0 ] ← -2
d [ 3, 2 ] ← 0

d	0	1	2	3	4
0	0	5	3	8	5
1	-4	0	-2	3	0
2	∞	∞	0	5	2
3	-2	2	0	0	-1
4	∞	∞	4	2	0

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

d	0	1	2	3	4
0	0	5	3	8	5
1	-4	0	-2	3	0
2	3	7	0	5	2
3	-2	2	0	0	-1
4	0	4	2	2	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

d	0	1	2	3	4
0	0	5	3	7	5
1	-4	0	-2	2	0
2	2	6	0	4	2
3	-2	2	0	0	-1
4	0	4	2	2	0

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

Algorytm Floyda-Warshalla znajdowania najmniejszych kosztów dojścia pomiędzy wszystkimi parami wierzchołków grafu ważonego

Wejście:

n	–	liczba wierzchołków w grafie, n ∈ C.
graf	–	zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.

Wyjście:

–

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.

Zmienne pomocnicze:

k, i, j

–

numery wierzchołków w grafie, k, i, j ∈ C.

Lista kroków:

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

Przykładowe programy

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 ):

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

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

Na początek: podrozdziału strony

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:

d	0	1	2	3	4
0	0	∞	∞	∞	∞
1	∞	0	∞	∞	∞
2	∞	∞	0	∞	∞
3	∞	∞	∞	0	∞
4	∞	∞	∞	∞	0

p	0	1	2	3	4
0	-1	-1	-1	-1	-1
1	-1	-1	-1	-1	-1
2	-1	-1	-1	-1	-1
3	-1	-1	-1	-1	-1
4	-1	-1	-1	-1	-1

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.

d	0	1	2	3	4
0	0	5	4	8	∞
1	-4	0	-2	∞	5
2	∞	∞	0	5	2
3	-1	2	∞	0	-1
4	∞	∞	4	2	0

p	0	1	2	3	4
0	-1	0	0	0	-1
1	1	-1	1	-1	1
2	-1	-1	-1	2	2
3	3	3	-1	-1	3
4	-1	-1	4	4	-1

d	0	1	2	3	4
0	0	5	4	8	∞
1	-4	0	-2	4	5
2	∞	∞	0	5	2
3	-1	2	3	0	-1
4	∞	∞	4	2	0

p	0	1	2	3	4
0	-1	0	0	0	-1
1	1	-1	1	0	1
2	-1	-1	-1	2	2
3	3	3	0	-1	3
4	-1	-1	4	4	-1

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

d	0	1	2	3	4
0	0	5	3	8	10
1	-4	0	-2	4	5
2	∞	∞	0	5	2
3	-2	2	0	0	-1
4	∞	∞	4	2	0

p	0	1	2	3	4
0	-1	0	1	0	1
1	1	-1	1	0	1
2	-1	-1	-1	2	2
3	1	3	1	-1	3
4	-1	-1	4	4	-1

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

d	0	1	2	3	4
0	0	5	3	8	5
1	-4	0	-2	3	0
2	∞	∞	0	5	2
3	-2	2	0	0	-1
4	∞	∞	4	2	0

p	0	1	2	3	4
0	-1	0	1	0	2
1	1	-1	1	2	2
2	-1	-1	-1	2	2
3	1	3	1	-1	3
4	-1	-1	4	4	-1

d	0	1	2	3	4
0	0	5	3	8	5
1	-4	0	-2	3	0
2	3	7	0	5	2
3	-2	2	0	0	-1
4	0	4	2	2	0

p	0	1	2	3	4
0	-1	0	1	0	2
1	1	-1	1	2	2
2	1	3	-1	2	2
3	1	3	1	-1	3
4	1	3	1	4	-1

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

d	0	1	2	3	4
0	0	5	3	7	5
1	-4	0	-2	2	0
2	2	6	0	4	2
3	-2	2	0	0	-1
4	0	4	2	2	0

p	0	1	2	3	4
0	-1	0	1	4	2
1	1	-1	1	4	2
2	1	3	-1	4	2
3	1	3	1	-1	3
4	1	3	1	4	-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:

p	0	1	2	3	4
0	-1	0	1	4	2
1	1	-1	1	4	2
2	1	3	-1	4	2
3	1	3	1	-1	3
4	1	3	1	4	-1

Wy:

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.

p	0	1	2	3	4
0	-1	0	1	4	2
1	1	-1	1	4	2
2	1	3	-1	4	2
3	1	3	1	-1	3
4	1	3	1	4	-1

Wy:

Poziom rekurencji 1:

i = 4, j = 1

Wywołujemy rekurencyjnie ten sam algorytm z parametrami:
i = 4, j = p [ 4, 1 ] = 3.

p	0	1	2	3	4
0	-1	0	1	4	2
1	1	-1	1	4	2
2	1	3	-1	4	2
3	1	3	1	-1	3
4	1	3	1	4	-1

Wy:

Poziom rekurencji 2:

i = 4, j = 3

Wywołujemy rekurencyjnie ten sam algorytm z parametrami:
i = 4, j = p [ 4, 3 ] = 4.

p	0	1	2	3	4
0	-1	0	1	4	2
1	1	-1	1	4	2
2	1	3	-1	4	2
3	1	3	1	-1	3
4	1	3	1	4	-1

Wy: 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.

Algorytm rozszerzony Floyda-Warshalla

Wejście:

n	–	liczba wierzchołków w grafie, n ∈ C.
graf	–	zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.

Wyjście:

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.

Zmienne pomocnicze:

k, i, j

–

numery wierzchołków w grafie, k, i, j ∈ C.

Lista kroków:

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

Algorytm rekurencyjnej procedury rekonstrukcji ścieżki z macierzy poprzedników p

FWPath ( p, i, j )

Wejście:

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.

Wyjście:

minimalna ścieżka od wierzchołka i-tego do j-tego lub napis "NO PATH", jeśli taka ścieżka nie istnieje

Lista kroków:

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

Przykładowe programy

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 ):

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

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

Na początek: podrozdziału strony

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.

Najkrótsze ścieżki pomiędzy wszystkimi parami wierzchołków w grafie ważonym
Algorytm Floyda-Warshalla

Problem

Wersja podstawowa

Algorytm Floyda-Warshalla znajdowania najmniejszych kosztów dojścia pomiędzy wszystkimi parami wierzchołków grafu ważonego

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy

Wersja rozszerzona

Algorytm rozszerzony Floyda-Warshalla

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Algorytm rekurencyjnej procedury rekonstrukcji ścieżki z macierzy poprzedników p

FWPath ( p, i, j )

Wejście:

Wyjście:

Lista kroków:

Przykładowe programy

Najkrótsze ścieżki pomiędzy wszystkimi parami wierzchołków w grafie ważonym Algorytm Floyda-Warshalla

Problem

Wersja podstawowa

Algorytm Floyda-Warshalla znajdowania najmniejszych kosztów dojścia pomiędzy wszystkimi parami wierzchołków grafu ważonego

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy

Wersja rozszerzona

Algorytm rozszerzony Floyda-Warshalla

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Algorytm rekurencyjnej procedury rekonstrukcji ścieżki z macierzy poprzedników p

FWPath ( p, i, j )

Wejście:

Wyjście:

Lista kroków:

Przykładowe programy

Najkrótsze ścieżki pomiędzy wszystkimi parami wierzchołków w grafie ważonym
Algorytm Floyda-Warshalla