Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Najkrótsza ścieżka w grafie ważonym
Algorytm Bellmana-Forda

SPIS TREŚCI

Problem

W spójnym grafie ważonym należy znaleźć najkrótsze ścieżki od wybranego wierzchołka startowego do wszystkich pozostałych wierzchołków.

Rozwiązanie

Jeśli ścieżki grafu posiadają nieujemne wagi, to najlepszym rozwiązaniem tego problemu jest przedstawiony w poprzednim rozdziale algorytm Dijkstry. W niektórych zastosowaniach ścieżki mogą posiadać wagi ujemne. W takim przypadku musimy użyć nieco mniej efektywnego, lecz bardziej wszechstronnego algorytmu Bellmana-Forda. Algorytm tworzy poprawny wynik tylko wtedy, gdy graf nie zawiera ujemnego cyklu ( ang. negative cycle ), czyli cyklu, w którym suma wag krawędzi jest ujemna. Jeśli taki cykl istnieje w grafie, to każdą ścieżkę można "skrócić" przechodząc wielokrotnie przez cykl ujemny. W takim przypadku algorytm Bellmana-Forda zgłasza błąd.

Opisany tutaj algorytm będzie tworzył dwie n-elementowe tablice danych ( n oznacza liczbę wierzchołków w grafie ):

  1. d  – element i-ty zawiera koszt dojścia z wierzchołka startowego do i-tego wierzchołka grafu po najkrótszej ścieżce. Dla wierzchołka startowego koszt dojścia wynosi 0.
  2. p  – element i-ty zawiera numer wierzchołka grafu, który jest poprzednikiem wierzchołka i-tego na najkrótszej ścieżce. Dla wierzchołka startowego poprzednikiem jest -1.

Na początku algorytmu ustawiamy wszystkie komórki tablicy d  na największą możliwą wartość ( oryginalnie na nieskończoność ) za wyjątkiem komórki odwzorowującej wierzchołek startowy, w której umieszczamy 0. Natomiast we wszystkich komórkach tablicy p  umieszczamy -1 ( w grafie nie ma wierzchołka o numerze -1, oznacza to zatem brak poprzednika ).

Następnie wykonujemy n  - 1 obiegów pętli, w której dokonujemy relaksacji krawędzi ( każdy obieg ustala koszt dojścia do przynajmniej jednego wierzchołka grafu, ponieważ wierzchołek startowy ma koszt 0, to pozostaje nam ustalenie kosztu jeszcze dla n  - 1 wierzchołków, stąd wymagane jest co najwyżej n - 1 obiegów pętli ). Polega ona na tym, iż przeglądamy po kolei wszystkie krawędzie grafu. Jeśli natrafimy na krawędź u–v  o wadze w, dla której koszt dojścia d [ v  ] jest większy od kosztu dojścia d [ u  ] + w ( czyli dojście do wierzchołka v  od wierzchołka u  tą krawędzią jest tańsze od poprzednio znalezionych dojść ), to ustawiamy koszt d [ v  ] na d [ u  ] + w  i w tablicy poprzedników dla p [ v  ] umieszczamy numer wierzchołka u. Gdy pętla wykona n  - 1 obiegów, w tablicy d  będziemy mieli koszty dojść do poszczególnych wierzchołków grafu po najkrótszych ścieżkach, a w tablicy p  dla każdego wierzchołka znajdziemy jego poprzednik na najkrótszej ścieżce od wierzchołka startowego.

Należy jeszcze sprawdzić, czy w grafie nie występuje cykl ujemny. W tym celu jeszcze raz przeglądamy zbiór krawędzi i jeśli natrafimy na krawędź u–v  o wadze w  dla której dalej koszt dojścia d [ v  ] jest większy od d [ u ] = w, to mamy do czynienia z cyklem ujemnym ( normalnie sytuacja taka nie może wystąpić, ponieważ relaksacja powinna ustawić d [ v  ] na d [ u  ] + w. Tylko w przypadku istnienia cyklu ujemnego relaksacja sobie z tym nie radzi ). W takim przypadku algorytm powinien zgłosić błąd.

Prześledźmy na przykładzie sposób pracy algorytmu Bellmana-Forda:

obrazek   Oto nasz graf ważony z ujemnymi wagami krawędzi.
obrazek
i 0 1 2 3 4 5
d [ i  ] 0
p [ i  ] -1 -1 -1 -1 -1 -1
Wybieramy na wierzchołek startowy wierzchołek o numerze zero. Policzymy koszty dojść do pozostałych wierzchołków po najkrótszych ścieżkach.
Tworzymy tablice d  i p, wypełniając je odpowiednio
obrazek
i 0 1 2 3 4 5
d [ i  ] 0 5
p [ i  ] -1 0 -1 -1 -1 -1
W pierwszym obiegu relaksujemy krawędź 0–1, dla której mamy:

d
[ 0 ] = 0
d [ 1 ] = ∞
d [ 1 ] > d [ 0 ] = 5

Ustawiamy:

d
[ 1 ] ← 0 + 5 = 5
p [ 1 ] ← 0 ( do wierzchołka 1 przychodzimy z wierzchołka 0 ).
obrazek
i 0 1 2 3 4 5
d [ i  ] 0 5 8 14
p [ i  ] -1 0 -1 1 1 -1
W drugim obiegu relaksujemy krawędzie 1–3 i 1–4.
d [ 1 ] = 5
d [ 3 ] = ∞
d [ 3 ] > d [ 1 ] + 3

d
[ 3 ] ← 5 + 3 = 8
p [ 3 ] ← 1
     d [ 1 ] = 5
d [ 4 ] = ∞
d [ 4 ] > d [ 1 ] = 9

d
[ 4 ] ← 5 + 9 = 14
p [ 4 ] ← 1
obrazek
i 0 1 2 3 4 5
d [ i  ] 0 5 13 8 11 9
p [ i  ] -1 0 4 1 3 4
W trzecim obiegu relaksujemy krawędzie 4–2, 4–5 i 3–4 ( zakładamy najbardziej niekorzystną kolejność relaksacji ).
d [ 4 ] = 14
d [ 2 ] = ∞
d [ 2 ] > d [ 4 ] + -1

d
[ 2 ] ← 14 + -1 = 13
p [ 2 ] ← 4
     d [ 4 ] = 14
d [ 5 ] = ∞
d [ 5 ] > d [ 4 ] + -5

d
[ 5 ] ← 14 + -5 = 9
p [ 5 ] ← 4
     d [ 3 ] = 8
d [ 4 ] = 14
d [ 4 ] > d [ 3 ] + 3

d
[ 4 ] ← 8 + 3 = 11
p [ 4 ] ← 3 ( zmiana! )
obrazek
i 0 1 2 3 4 5
d [ i  ] 0 5 10 8 11 6
p [ i  ] -1 0 4 1 3 4
W czwartym obiegu relaksujemy krawędzie 4–2 i 4–5
d [ 4 ] = 11
d [ 2 ] = 13
d [ 2 ] > d [ 4 ] + -1

d
[ 2 ] ← 11 + -1 = 10
p [ 2 ] ← 4
     d [ 4 ] = 11
d [ 5 ] = 9
d [ 5 ] > d [ 4 ] + -5

d
[ 5 ] ← 11 + -5 = 6
p [ 5 ] ← 4
obrazek
i 0 1 2 3 4 5
d [ i  ] 0 5 10 8 11 6
p [ i  ] -1 0 4 1 3 4
Obieg piąty nie wprowadzi już żadnych zmian, ponieważ warunek relaksacji nie będzie spełniony dla żadnej z krawędzi ( pętlę relaksacji można przerwać, jeśli w danym obiegu algorytm nie wprowadził żadnych dalszych zmian do tablic d  i p  ). Tablica d  zawiera zatem minimalne koszty dojścia od wierzchołka 0 do poszczególnych wierzchołków w grafie. Tablica p  zawiera informacje o najkrótszych ścieżkach wiodących od wierzchołka 0 do pozostałych wierzchołków.

Graf nie posiada ujemnych cykli.

Algorytm Bellmana-Forda znajdowania najkrótszych ścieżek w spójnym, skierowanym grafie ważonym

Wejście:

n  –  liczba wierzchołków w grafie, n  ∈ C.
graf  –  zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje. Graf musi być spójny.
v  –  numer wierzchołka startowego, v  ∈ C.

Wyjście:

true:
d  –  n  elementowa tablica z kosztami dojścia. Element d [ i  ] zawiera koszt najkrótszej ścieżki od wierzchołka v  do i.
p  –  n  elementowa tablica poprzedników. Element p [ i  ] zawiera numer wierzchołka, który jest poprzednikiem wierzchołka i-tego na najkrótszej ścieżce od wierzchołka v  do i. Element p [ v  ] = -1, ponieważ wierzchołek startowy nie posiada poprzednika..

false:

graf zawiera ujemny cykl, który uniemożliwia wyznaczenie najkrótszych ścieżek ( każda ścieżka może być najkrótszą, jeśli przepuścimy ją odpowiednią liczbę razy przez cykl ujemny ).

Zmienne pomocnicze:
x, y  –  numery wierzchołków w grafie, x, y  ∈ C.
i  –  licznik pętli, i  ∈ C.
test  –  logiczna zmienna decyzyjna.

Lista kroków:

K01: Utwórz n  elementową tablicę d
i wypełnij ją największą liczbą
 
K02: Utwórz n  elementową tablicę p
i wypełnij ją liczbami -1
 
K03: d [ v  ] ← 0 koszt dojścia do wierzchołka startowego
K04: Dla i  = 2, 3, ..., n :
wykonuj
kroki K05...K12
pętlę główną wykonujemy co najwyżej n - 1 razy
K05:     test  ← true zmienna przechowuje informację o zmianach
K06:     Dla x  = 0, 1, ..., n - 1:
    wykonuj kroki K07...K11
 
K07:         Dla każdego sąsiada y  wierzchołka x :
        wykonuj kroki K08...K11
 
K08:             Jeśli d [ y  ] ≤ d [ x  ] + waga krawędzi x-y,
            to następny obieg pętli K07
sprawdzamy warunek relaksacji krawędzi
K09:             test  ← false zapamiętujemy zmianę
K10:             d [ y  ] ← d [ x  ] + waga krawędzi x-y dokonujemy relaksacji krawędzi
K11:             p [ y  ] ← x ustawiamy poprzednik wierzchołka y na x
K12:     Jeśli test  = true,
    to zakończ z wynikiem true
wynik w d i p
K13: Dla x  = 0, 1, ..., n  - 1:
wykonuj
krok K14
sprawdzamy istnienie ujemnego cyklu
K14:     Dla każdego sąsiada y  wierzchołka x :
    wykonuj:
        Jeśli d [ y  ] > d [ x  ] + waga krawędzi x-y,
        to zakończ z wynikiem false
ujemny cykl!!!
K15: Zakończ z wynikiem true  

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 do poszczególnych wierzchołków grafu za pomocą algorytmu Bellmana-Forda. Definicja danych wejściowych jest następująca:

W pierwszym wierszu program odczytuje kolejno numer wierzchołka startowego v, 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 i druga liczba określa wierzchołki grafu, które są ze sobą połączone tą krawędzią – krawędź biegnie od wierzchołka x  do wierzchołka y. Trzecia liczba jest wagą krawędzi w.
 
Dane przykładowe ( przekopiuj do schowka i wklej do okna konsoli ):
obrazek      0 6 11
0 1 5
1 3 3 1 4 9
2 0 3 2 1 -4
3 4 3 3 5 2
4 2 -1 4 5 -5
5 0 9 5 2 8
Pascal
// Algorytm Bellmana-Forda
// Data   : 13.04.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program bellman_ford;

// Typy danych
type
  PslistEl = ^slistEl;
  slistEl = record
    next : PslistEl;
    v, w  : integer;
  end;

// Zmienne globalne
var
  m, n : integer;                 // Liczba krawędzi i wierzchołków w grafie
  A : array of PslistEl;          // Tablica dynamiczna list sąsiedztwa
  d : array of int64;             // Tablica kosztów dojścia
  p : array of integer;           // Tablica poprzedników

// Funkcja wyznacza najkrótsze ścieżki
// v - wierzchołek startowy
// Wyjście:
// true  - wyniki w d i p
// false - graf zawiera ujemny cykl
//------------------------------------
function BF ( v : integer ) : boolean;
var
  i, x : integer;
  test : boolean;
  pv : PslistEl;
begin
  d [ v ] := 0;                   // Zerujemy koszt dojścia do v
  for i := 2 to n do              // Pętla relaksacji
  begin
    test := true;                 // Oznacza, że algorytm nie wprowadził zmian do d i p
    for x := 0 to n - 1 do        // Przechodzimy przez kolejne wierzchołki grafu
    begin
      pv := A [ x ];              // Przeglądamy listę sąsiadów wierzchołka x
      while pv <> nil do
      begin
        if d [ pv^.v ] > d [ x ] = pv^.w then // Sprawdzamy warunek relaksacji
        begin
          test := false;          // Jest zmiana w d i p
          d [ pv^.v ] := d [ x ] + pv^.w; // Relaksujemy krawędź z x do jego sąsiada
          p [ pv^.v ] := x;       // Poprzednikiem sąsiada będzie x
        end;
        pv := pv^.next;           // Następny sąsiad
      end;
      if test then Exit ( true ); // Jeśli nie było zmian, to kończymy
    end;
  end;

  // Sprawdzamy istnienie ujemnego cyklu

  for x := 0 to n - 1 do
  begin
    pv := A [ x ];
    while pv <> nil do
    begin
      if d [ pv^.v ] > d [ x ] + pv^.w then Exit ( false ); // ujemny cykl!!
      pv := pv^.next;
    end;
  end;
  BF := true;
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************
var
  S : array of integer;    // Stos
  i, v, x, y, w, sptr : integer;
  rv, pv : PslistEl;
begin
  read ( v, n, m );        // Wierzchołek startowy, liczba wierzchołków i krawędzi

  SetLength ( A, n );      // Tworzymy tablicę list sąsiedztwa
  SetLength ( d, n );      // Tworzymy tablicę kosztów dojścia
  SetLength ( p, n );      // Tworzymy tablice poprzedników
  for i := 0 to n - 1 do   // Inicjujemy struktury danych
  begin
    d [ i ] := MAXINT;
    p [ i ] := -1;
    A [ i ] := nil;
  end;

  for i := 1 to m do
  begin
    read ( x, y, w );      // Czytamy wierzchołki krawędzi oraz jej wagę
    new ( pv );            // Tworzymy element listy
    pv^.v := y;            // Inicjujemy go
    pv^.w := w;
    pv^.next := A [ x ];   // Dodajemy go na początek listy sąsiadów wierzchołka x
    A [ x ] := pv;
  end;

  writeln;

  // Wyznaczamy najkrótsze ścieżki algorytmem Bellmana-Forda

  if BF ( v ) then
  begin
    SetLength ( S, n );    // Tworzymy prosty stos
    sptr := 0;
    for i := 0 to n - 1 do
    begin
      write ( i, ': ' );
      x := i;              // Wierzchołki ścieżki umieszczamy na stosie
      repeat               // w kolejności od ostatniego do pierwszego
        S [ sptr ] := x;
        inc ( sptr );
        x := p [ x ];
      until x = -1;

      while sptr > 0 do    // Wierzchołki ze stosu drukujemy
      begin                // w kolejności od pierwszego do ostatniego
        dec ( sptr );
        write ( S [ sptr ], ' ' );
      end;

      writeln ( '$', d [ i ] ); // Na końcu wyświetlamy koszt
    end;
    SetLength ( S, 0 );    // Usuwamy stos
  end
  else writeln ( 'Negative Cycle found!' );

  // Usuwamy struktury dynamiczne

  for i := 0 to n - 1 do
  begin
    pv := A [ i ];
    while pv <> nil do
    begin
      rv := pv;
      pv := pv^.next;
      dispose ( rv );
    end;
  end;

  SetLength ( A, 0 );
  SetLength ( d, 0 );
  SetLength ( p, 0 );
end.
C++
// Algorytm Bellmana-Forda
// Data   : 13.04.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>

using namespace std;

const int MAXINT = 2147483647; // Największa liczba całkowita

// Typy danych
struct slistEl
{
  slistEl * next;
  int v, w;
};

// Zmienne globalne
int m, n;      // Liczba krawędzi i wierzchołków w grafie
slistEl ** A;  // Tablica dynamiczna list sąsiedztwa
long long * d; // Tablica kosztów dojścia
int * p;       // Tablica poprzedników

// Funkcja wyznacza najkrótsze ścieżki
// v - wierzchołek startowy
// Wyjście:
// true  - wyniki w d i p
// false - graf zawiera ujemny cykl
//------------------------------------
bool BF ( int v )
{
  int i, x;
  bool test;
  slistEl * pv;

  d [ v ] = 0;               // Zerujemy koszt dojścia do v
  for( i = 1; i < n; i++ )   // Pętla relaksacji
  {
    test = true;             // Oznacza, że algorytm nie wprowadził zmian do d i p
    for( x = 0; x < n; x++ ) // Przechodzimy przez kolejne wierzchołki grafu
      for( pv = A [ x ]; pv; pv = pv->next ) // Przeglądamy listę sąsiadów wierzchołka x
        if( d [ pv->v ] > d [ x ] + pv->w ) // Sprawdzamy warunek relaksacji
        {
          test = false;      // Jest zmiana w d i p
          d [ pv->v ] = d [ x ] + pv->w; // Relaksujemy krawędź z x do jego sąsiada
          p [ pv->v ] = x;   // Poprzednikiem sąsiada będzie x
        }
    if( test ) return true;  // Jeśli nie było zmian, to kończymy
  }

  // Sprawdzamy istnienie ujemnego cyklu

  for( x = 0; x < n; x++ )
    for( pv = A [ x ];pv;pv = pv->next )
      if( d [ pv->v ] > d [ x ] + pv->w ) return false; // ujemny cykl!!

  return true;
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************
int main( )
{
  int i, v, x, y, w, sptr, *S;
  slistEl *rv, *pv;

  cin >> v >> n >> m;      // Wierzchołek startowy, liczba wierzchołków i krawędzi

  A = new slistEl * [ n ]; // Tworzymy tablicę list sąsiedztwa
  d = new long long [ n ]; // Tworzymy tablicę kosztów dojścia
  p = new int [ n ];       // Tworzymy tablice poprzedników
  for( i = 0; i < n; i++ ) // Inicjujemy struktury danych
  {
    d [ i ] = MAXINT;
    p [ i ] = -1;
    A [ i ] = NULL;
  }

  for( i = 0; i < m; i++ )
  {
    cin >> x >> y >> w; // Czytamy wierzchołki krawędzi oraz jej wagę
    pv = new slistEl;   // Tworzymy element listy
    pv->v = y;          // Inicjujemy go
    pv->w = w;
    pv->next = A [ x ]; // Dodajemy go na początek listy sąsiadów wierzchołka x
    A [ x ] = pv;
  }

  cout << endl;

  // Wyznaczamy najkrótsze ścieżki algorytmem Bellmana-Forda

  if( BF ( v ) )
  {
    S = new int [ n ];    // Tworzymy prosty stos
    sptr = 0;

    for( i = 0; i < n; i++ )
    {
      cout << i << ": ";
      for( x = i;x != -1;x = p [ x ] ) // Wierzchołki ścieżki umieszczamy na stosie
        S [ sptr++ ] = x; // w kolejności od ostatniego do pierwszego

      while( sptr )       // Wierzchołki ze stosu drukujemy
        cout << S [ --sptr ] << " "; // w kolejności od pierwszego do ostatniego

      cout << "$" << d [ i ] << endl; // Na końcu wyświetlamy koszt
    }
    delete [ ] S;         // Usuwamy stos
  }
  else cout << "Negative Cycle found!" << endl;

  // Usuwamy struktury dynamiczne

  for( i = 0; i < n; i++ )
  {
    pv = A [ i ];
    while( pv )
    {
      rv = pv;
      pv = pv->next;
      delete rv;
    }
  }

  delete [ ] A;
  delete [ ] d;
  delete [ ] p;

  return 0;
}
Basic
' Algorytm Bellmana-Forda
' Data   : 13.04.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

const MAXINT = 2147483647         ' Największa liczba całkowita

' Typy danych
Type slistEl
  Next As slistEl Ptr
  v As Integer
  w As Integer
End Type

' Zmienne globalne
Dim Shared As Integer m, n         ' Liczba krawędzi i wierzchołków w grafie
Dim Shared As slistEl Ptr Ptr A   ' Tablica dynamiczna list sąsiedztwa
Dim Shared As LongInt Ptr d       ' Tablica kosztów dojścia
Dim Shared As Integer Ptr p       ' Tablica poprzedników

' Funkcja wyznacza najkrótsze ścieżki
' v - wierzchołek startowy
' Wyjście:
' true  - wyniki w d i p
' false - graf zawiera ujemny cykl
'------------------------------------
Function BF ( ByVal v As integer ) As Integer
  Dim As Integer i, x, test
  Dim As slistEl Ptr pv

  d [ v ] = 0          ' Zerujemy koszt dojścia do v
  For i = 2 To n       ' Pętla relaksacji
    test = 1           ' Oznacza, że algorytm nie wprowadził zmian do d i p
    For x = 0 To n - 1 ' Przechodzimy przez kolejne wierzchołki grafu
      pv = A [ x ] 
      While pv         ' Przeglądamy listę sąsiadów wierzchołka x
        If d [ pv->v ] > d [ x ] + pv->w Then ' Sprawdzamy warunek relaksacji
          test = 0     ' Jest zmiana w d i p
          d [ pv->v ] = d [ x ] + pv->w ' Relaksujemy krawędź z x do jego sąsiada
          p [ pv->v ] = x ' Poprzednikiem sąsiada będzie x
        End If
        pv = pv->Next  ' Następny sąsiad
      Wend
    Next
    If test = 1 Then Return 1 ' Jeśli nie było zmian, to kończymy
  Next

  ' Sprawdzamy istnienie ujemnego cyklu

  For x = 0 To n - 1
    pv = A [ x ] 
    While pv
      If d [ pv->v ] > d [ x ] + pv->w Then Return 0 ' ujemny cykl!!
      pv = pv->Next
    Wend
  Next
  
  return 1
End Function

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As Integer i, v, x, y, w, sptr
Dim As Integer Ptr S
Dim As slistEl Ptr rv, pv

Open Cons For Input As #1

Input #1, v, n, m     ' Wierzchołek startowy, liczba wierzchołków i krawędzi

A = New slistEl Ptr [ n ] ' Tworzymy tablicę list sąsiedztwa
d = New LongInt [ n ] ' Tworzymy tablicę kosztów dojścia
p = New integer [ n ] ' Tworzymy tablice poprzedników

For i = 0 To n - 1    ' Inicjujemy struktury danych
  d [ i ] = MAXINT
  p [ i ] = -1
  A [ i ] = 0
Next

For i = 0 To m - 1
  Input #1, x, y, w  ' Czytamy wierzchołki krawędzi oraz jej wagę
  pv = New slistEl   ' Tworzymy element listy
  pv->v = y          ' Inicjujemy go
  pv->w = w
  pv->next = A [ x ] ' Dodajemy go na początek listy sąsiadów wierzchołka x
  A [ x ] = pv
Next

Close #1

Print

' Wyznaczamy najkrótsze ścieżki algorytmem Bellmana-Forda

If BF ( v ) = 1 Then
  S = New Integer [ n ]      ' Tworzymy prosty stos
  sptr = 0

  For i = 0 To n - 1
    Print Using "&: ";i;
    x = i
    While x <> -1            ' Wierzchołki ścieżki umieszczamy na stosie
      S [ sptr ] = x         ' w kolejności od ostatniego do pierwszego
      sptr += 1
      x = p [ x ] 
    Wend
    
    While sptr > 0           ' Wierzchołki ze stosu drukujemy
      sptr -= 1
      Print Using "& ";S [ sptr ]; ' w kolejności od pierwszego do ostatniego
    Wend
    
    Print using "$&";d [ i ] ' Na końcu wyświetlamy koszt
  Next
  
  Delete [ ] S               ' Usuwamy stos
Else
  Print "Negative Cycle found!"
EndIf

Print

' Usuwamy struktury dynamiczne

For i = 0 To n - 1
  pv = A [ i ] 
  While pv
    rv = pv
    pv = pv->Next
    Delete rv
  Wend
Next

Delete [ ] A
Delete [ ] d
Delete [ ] p

End
Wynik:
0 6 11
0 1 5
1 3 3 1 4 9
2 0 3 2 1 -4
3 4 3 3 5 2
4 2 -1 4 5 -5
5 0 9 5 2 8

0: 0 $0
1: 0 1 $5
2: 0 1 3 4 2 $10
3: 0 1 3 $8
4: 0 1 3 4 $11
5: 0 1 3 4 5 $6
obrazek

Algorytm Bellmana-Forda zawodzi, gdy graf zawiera cykl ujemny. Z drugiej strony możemy wykorzystać ten algorytm właśnie do wykrywania istnienia cyklu ujemnego w grafie.

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 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.