Algorytmy i Struktury Danych - Algorytm Bellmana-Forda

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

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

Oto nasz graf ważony z ujemnymi wagami krawędzi.

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

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

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

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

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

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

Elementy 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: ; pętlę główną wykonujemy co najwyżej n-1 razy
     wykonuj kroki K05…K12
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, ; sprawdzamy
           to następny obieg pętli K07 ; 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, ; wynik w d i p
       to zakończ z wynikiem true
K13: Dla x = 0, 1, …, n-1: ; sprawdzamy istnienie ujemnego cyklu
     wykonuj krok K14
K14:   Dla każdego sąsiada y wierzchołka x :
       wykonuj:
         Jeśli d[y] > d[x]+waga krawędzi x-y, ; ujemny cykl!!!
         to zakończ z wynikiem false
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):

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
  PSLel = ^SLel;
  SLel = record
    next : PSLel;
    v, w : integer;
  end;

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

// 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 : PSLel;

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

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************
var
  // Stos
  S : array of integer;
  i,v,x,y,w,sptr : integer;
  rv,pv : PSLel;
begin
  // Wierzchołek startowy,
  // liczba wierzchołków
  // i krawędzi
  read(v, n, m);
  // Tworzymy tablicę
  // list sąsiedztwa
  SetLength(A, n);
  // Tworzymy tablicę
  // kosztów dojścia
  SetLength(d, n);
  // Tworzymy tablice
  // poprzedników
  SetLength(p, n);
  // Inicjujemy struktury
  // danych
  for i := 0 to n-1 do
  begin
    d[i] := MAXINT;
    p[i] := -1;
    A[i] := nil;
  end;
  for i := 1 to m do
  begin
    // Czytamy wierzchołki
    // krawędzi oraz jej wagę
    read(x, y, w);
    // Tworzymy element listy
    new(pv);
    // Inicjujemy go
    pv^.v := y;
    pv^.w := w;
    // Dodajemy go na początek
    // listy sąsiadów wierzchołka x
    pv^.next := A[x];
    A[x] := pv;
  end;
  writeln;
  // Wyznaczamy najkrótsze ścieżki
  // algorytmem Bellmana-Forda
  if BF(v) then
  begin
    // Tworzymy prosty stos
    SetLength(S, n);
    sptr := 0;
    for i := 0 to n-1 do
    begin
      write(i, ': ');
      // Wierzchołki ścieżki
      // umieszczamy na stosie
      x := i;
      // w kolejności
      // od ostatniego
      // do pierwszego
      repeat
        S[sptr] := x;
        inc(sptr);
        x := p[x];
      until x = -1;
      // Wierzchołki
      // ze stosu drukujemy
      while sptr > 0 do
      // w kolejności
      // od pierwszego
      // do ostatniego
      begin
        dec(sptr);
        write(S[sptr], ' ');
      end;
      // Na końcu
      // wyświetlamy koszt
      writeln('$', d[i]);
    end;
    // Usuwamy stos
    SetLength(S, 0);
  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;

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

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

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

// 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;
  SLel * pv;

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

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

  // Wierzchołek startowy,
  // liczba wierzchołków
  // i krawędzi
  cin >> v >> n >> m;
  // Tworzymy tablicę
  // list sąsiedztwa
  A = new SLel * [n];
  // Tworzymy tablicę
  // kosztów dojścia
  d = new long long [n];
  // Tworzymy tablicę
  // poprzedników
  p = new int [n];
  // Inicjujemy
  // struktury danych
  for(i = 0; i < n; i++)
  {
    d[i] = MAXINT;
    p[i] = -1;
    A[i] = nullptr;
  }
  for(i = 0; i < m; i++)
  {
    // Czytamy wierzchołki
    // krawędzi oraz jej wagę
    cin >> x >> y >> w;
    // Tworzymy element listy
    pv = new SLel;
    // Inicjujemy go
    pv->v = y;
    pv->w = w;
    // Dodajemy go na początek
    // listy sąsiadów
    // wierzchołka x
    pv->next = A[x];
    A[x] = pv;
  }
  cout << endl;
  // Wyznaczamy najkrótsze
  // ścieżki algorytmem
  // Bellmana-Forda
  if(BF(v))
  {
    // Tworzymy prosty stos
    S = new int [n];
    sptr = 0;
    for(i = 0; i < n; i++)
    {
      cout << i << ": ";
      // Wierzchołki ścieżki
      // umieszczamy na stosie
      for(x = i;x != -1;x = p[x])
        // w kolejności
        // od ostatniego
        // do pierwszego
        S[sptr++] = x;
      // Wierzchołki
      // ze stosu drukujemy
      while(sptr)
        // w kolejności
        // od pierwszego
        // do ostatniego
        cout << S[--sptr] << " ";
      // Na końcu wyświetlamy koszt
      cout << "$" << d[i] << endl;
    }
    // Usuwamy stos
    delete [] S;
  }
  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
'---------------------------

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

' Typy danych
Type SLel
  next As SLel Ptr
  v As Integer
  w As Integer
End Type

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

' 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 SLel Ptr pv

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

Open Cons For Input As #1
' Wierzchołek startowy,
' liczba wierzchołków
' i krawędzi
Input #1, v, n, m
' Tworzymy tablicę
' list sąsiedztwa
A = New SLel Ptr [n]
' Tworzymy tablicę
' kosztów dojścia
d = New LongInt [n]
' Tworzymy tablicę
' poprzedników
p = New integer [n]
' Inicjujemy
' struktury danych
For i = 0 To n-1
  d[i] = MAXINT
  p[i] = -1
  A[i] = 0
Next
For i = 0 To m-1
  ' Czytamy wierzchołki
  ' krawędzi oraz jej wagę
  Input #1, x, y, w
  ' Tworzymy element listy
  pv = New SLel
  ' Inicjujemy go
  pv->v = y
  pv->w = w
  ' Dodajemy go na początek
  ' listy sąsiadów wierzchołka x
  pv->next = A[x]
  A[x] = pv
Next
Close #1
Print
' Wyznaczamy najkrótsze
' ścieżki algorytmem
' Bellmana-Forda
If BF(v) = 1 Then
  ' Tworzymy prosty stos
  S = New Integer [n]
  sptr = 0
  For i = 0 To n-1
    Print Using "&: ";i;
    x = i
    ' Wierzchołki ścieżki
    ' umieszczamy na stosie
    While x <> -1
      ' w kolejności
      ' od ostatniego
      ' do pierwszego
      S[sptr] = x
      sptr += 1
      x = p[x]
    Wend
    ' Wierzchołki
    ' ze stosu drukujemy
    While sptr > 0
      sptr -= 1
      ' w kolejności
      ' od pierwszego
      ' do ostatniego
      Print Using "& ";S[sptr];
    Wend
    ' Na końcu wyświetlamy koszt
    Print using "$&";d[i]
  Next
  ' Usuwamy stos
  Delete [] S
Else
  Print "Negative Cycle found!"
EndIf
Print
' Usuwamy
' struktury dynamiczne
For i = 0 To n-1
  pv = A[i]
  While pv <> 0
    rv = pv
    pv = pv->next
    Delete rv
  Wend
Next
Delete [] A
Delete [] d
Delete [] p
End

Python (dodatek)

# Algorytm Bellmana-Forda
# Data: 17.02.2025
# (C)2025 mgr Jerzy Wałaszek
#---------------------------

# Największa liczba całkowita
MAXINT = 2147483647

# Klasa listy
class SLel:
    def __init__(self):
        self.next = None
        self.v = 0
        self.w = 0


# Funkcja wyznacza najkrótsze ścieżki
# v - wierzchołek startowy
# Wyjście:
# true - wyniki w d i p
# false - graf zawiera ujemny cykl
#------------------------------------
def bf(v):
    global d,a,p
    # Zerujemy koszt dojścia do v
    d[v] = 0
    # Pętla relaksacji
    for i in range(2,n+1):
        # Oznacza, że algorytm
        # nie wprowadził zmian
        # do d i p
        test = True
        # Przechodzimy przez
        # kolejne wierzchołki
        # grafu
        for x in range(n):
            pv = a[x]
            # Przeglądamy listę
            # sąsiadów wierzchołka x
            while pv:
                # Sprawdzamy
                # warunek relaksacji
                if d[pv.v] > d[x]+pv.w:
                    # Jest zmiana w d i p
                    test = False
                    # Relaksujemy krawędź
                    # z x do jego sąsiada
                    d[pv.v] = d[x]+pv.w
                    # Poprzednikiem
                    # sąsiada będzie x
                    p[pv.v] = x
                # Następny sąsiad
                pv = pv.next
        # Jeśli nie było zmian,
        # to kończymy
        if test: return True
    # Sprawdzamy istnienie
    # ujemnego cyklu
    for x in range(n):
        pv = a[x]
        while pv:
            # ujemny cykl!
            if d[pv.v] > d[x]+pv.w:
                return False
            pv = pv.next
    return True


# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

# Wierzchołek startowy,
# liczba wierzchołków
# i krawędzi
z = input().split()
v = int(z[0])
n = int(z[1])
m = int(z[2])
# Tworzymy tablicę
# list sąsiedztwa
a = [None] * n
# Tworzymy tablicę
# kosztów dojścia
d = [MAXINT] * n
# Tworzymy tablicę
# poprzedników
p = [-1] * n
for i in range(m):
    # Czytamy wierzchołki
    # krawędzi oraz jej wagę
    z = input().split()
    x = int(z[0])
    y = int(z[1])
    w = int(z[2])
    # Tworzymy element listy
    pv = SLel()
    # Inicjujemy go
    pv.v = y
    pv.w = w
    # Dodajemy go na początek
    # listy sąsiadów wierzchołka x
    pv.next = a[x]
    a[x] = pv
print()
# Wyznaczamy najkrótsze
# ścieżki algorytmem
# Bellmana-Forda
if bf(v):
    # Tworzymy prosty stos
    s = [0] * n
    sptr = 0
    for i in range(n):
        print(i,": ",sep="",end="")
        x = i
        # Wierzchołki ścieżki
        # umieszczamy na stosie
        while x != -1:
            # w kolejności
            # od ostatniego
            # do pierwszego
            s[sptr] = x
            sptr += 1
            x = p[x]
        # Wierzchołki
        # ze stosu drukujemy
        while sptr:
            sptr -= 1
            # w kolejności
            # od pierwszego
            # do ostatniego
            print(s[sptr],end=" ")
        # Na końcu wyświetlamy koszt
        print("$",d[i],sep="")
    # Usuwamy stos
    del s
else:
    print("Negative Cycle found!")
print()
# Usuwamy
# struktury dynamiczne
for i in range(n):
    while a[i]:
        a[i] = a[i].next
del a,d,p

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

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.

do podrozdziału do 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ótsza ścieżka w grafie ważonym
Algorytm Bellmana-Forda

Problem

Rozwiązanie

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

Wejście:

Wyjście:

true:

false:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

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

Problem

Rozwiązanie

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

Wejście:

Wyjście:

true:

false:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

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