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


Tematy pokrewne  
Grafy
Podstawowe pojęcia dotyczące grafów
Reprezentacja grafów w komputerze
Przechodzenie grafów w głąb – DFS
Przechodzenie grafów wszerz – BFS
Transpozycja grafu
Kwadrat grafu
Graf krawędziowy
Stopień grafu
Znajdowanie ścieżki w grafie
Znajdowanie drogi w labiryncie
Spójność grafu
Znajdowanie spójnych składowych w grafie
Znajdowanie silnie spójnych składowych w grafie
Drzewa rozpinające grafu
Znajdowanie mostów w grafie
Znajdowanie punktów artykulacji w grafie
Grafy dwudzielne
Kojarzenie małżeństw
Cykliczność grafu
Znajdowanie cykli w grafie
Istnienie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Hamiltona
Sortowanie topologiczne grafu skierowanego
Najkrótsza ścieżka w grafie ważonym – algorytm Dijkstry
Najkrótsza ścieżka w grafie ważonym – algorytm Bellmana-Forda
Najkrótsze ścieżki pomiędzy wszystkimi parami wierzchołków w grafie ważonym
Problem chińskiego listonosza
Problem komiwojażera
Minimalne drzewo rozpinające
Kolorowanie grafu
Znajdowanie klik w grafie
 

Problem

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

 

 

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:

 

  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 symbol C
graf  –  zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje. Graf musi być spójny.
v  –  numer wierzchołka startowego, v symbol 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 symbol C
i  –  licznik pętli, i symbol 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 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 K07...K11  
K07:         Dla każdego sąsiada y wierzchołka x wykonuj 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 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  

 

Program

Ważne:

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.

 

Przykładowe dane:

     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

 

Lazarus
// 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.
Code::Blocks
// 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;
}
Free 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

 

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.

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.