Algorytm Bellmana-Forda

Z RNO-Wiki

Spis treści

Problem najkrótszych ścieżek z jednym źródłem

Rozważmy tym razem graf skierowany $$G=<V,E>$$ z funkcją wagową $$f:E\to R$.

Rysunek
DAG.png
przedstawia przykład takiego grafu. Wagi krawędzi oznaczono kolorem niebieskiem.

Często grafy tego typu mogą reprezentować pewną sieć połączeń, np. między miastami, gdzie wagi oznaczają np. dystans albo raczej koszt przejazdu pomiędzy miastami, bo dystans zwykle nie jest ujemny.

W artykule tym zajmiemy się problemem znajdowania najkrótszych ścieżek z jednego źródła w grafie $$G$$, tj. problemem, w którym dla danego wyróżnionego wierzchołka $$s$$ - źródła (ang. source), chcemy wyznaczyć najkrótsze ścieżki do wszystkich pozostałych wierzchołków w grafie $$G$$; koszt ścieżki definiujemy jako sumę wag wszystkich jej krawędzi.

Na przykład, dla grafu z powyższego rysunku i źródła w wierzchołku 1, najkrótsze ścieżki można przedstawić w następujący sposób:

ShorthestPaths.png

Aby znaleźć najkrótszą ścieżkę do wierzchołka 2, wystarczy rozpocząć przeglądanie grafu od wierzchołka 2, chodząc wstecz po krawędziach pomarańczowych, aż do napotkania wierzchołka źródłowego. Na poniższym rysunku zaznaczono odwiedzone krawędzie, które tworzą najkrótszą ścieżkę do wierzchołka 2.

ShortestPath.png

Można teraz zauważyć pewną rzecz, która wcale nie wyszła tutaj przypadkowo. Najkrótsze ścieżki do wierzchołków leżących na czerwonej ścieżce zawierają się w niej, tzn. jeśli

s -> u_1 -> u_2 -> ... -> u_k

jest najkrótszą ścieżką do wierzchołka u_k, to

s -> u_1 -> u_2 -> ... -> u_j  (j<k)

jest najkrótszą ścieżką do u_j.

Dowód tego faktu pozostawiamy czytelnikowi.

Cykle ujemne

Zanim przejdziemy do rozwiązania naszego problemu, podkreślmy, że w naszych rozważaniach dopuszczamy ujemne wartości wag na krawędziach w grafie skierowanym. W związku z tym, może się zdarzyć, że w danym grafie istnieje cykl ujemny, tj. cykl, którego suma wag krawędzi jest liczbę ujemną. Wówczas nie da się prawidłowo zdefiniować najkrótszej ścieżki do pewnych wierzchołków, gdyż zawsze można wykonać kilka okrążeń więcej, aby uzyskać coraz krótsze ścieżki. Wobec tego ograniczamy się jedynie do takich grafów, w których nie istnieją cykle ujemne. Później, w rozdziale #Znajdowanie cykli ujemnych, spróbujemy rozwiązać problem sprawdzania tego warunku.

Algorytm Bellmana-Forda

W związku z tym, że wagi krawędzi mogą być liczbami ujemnymi, nie możemy rozwiązać rozważanego problemu za pomocą Algorytmu Dijkstry. W rozdziale tym przedstawimy algorytm Bellmana-Forda; zob. np. Wikipedia, ang.

Wprowadźmy oznaczenie

 D[u] := długość najkrótszej ścieżki ze źródła do wierzchołka u.

Na początek, skupmy się na wyznaczeniu wartości D[u] dla wszystkich wierzchołków w grafie.

Algorytm opiera się na bardzo prostej obserwacji:

 Obserwacja 1
 dla każdej krawędzi u->v
  D[u] + waga(u->v)  =>  D[v]

Można także udowodnić twierdzenie odwrotne, tzn. jeśli zachodzi powyższa obserwacja, to funkcja D[u] jest funkcją najkrótszych odległości od źródła s.

Zapis algorytmu w pseudo języku jest więc następujący

 Dla każdego wierzchołka u \in V, wykonaj D[u] := \infty
 D[s] := 0;
 Dopóki istnieje krawędź  u->n, dla której D[u]+waga(u->v) < D[v], wykonaj
    D[v] := D[u]+waga(u,v)
 

Implementacja


#include<cstdio>
#include<vector>
 
using namespace std;
 
int n, m, s; //n - liczba wierzchołków, m - liczba krawędzi, s - punkt, z którego zaczynamy
 
vector<vector<int> >E;
vector<int>D;
 
const int INF = (1 << 30); //Jest to wartość na tyle duża, że dla liczb z zakresu int powinna posłużyć jako nieskończoność
 
int main()
{
    scanf("%d %d %d", &n, &m, &s); // wczytujemy podstawowe informacje ze standardowego wejścia
 
    E.resize(m);
 
    for (int i = 0; i < m; i++) //wczytywanie opisu grafu
    {
        int u , v, waga;
 
        scanf("%d %d %d", &u, &v, &waga);
        E[i].resize(3);
        E[i][0] = u;
        E[i][1] = v;
        E[i][2] = waga;
    }
 
    D.resize(n);
 
    for (int i = 0; i < n; i++) D[i]=INF; //D jest tablicą, w której trzymamy "koszt" dotarcia do danego wierzchołka z wierzchołka s. Na początku zakładamy, że dotarcie do reszty wierzchołków jest bardzo drogie
    D[s] = 0; //ale do wierzchołka s możemy dostać się za darmo
    for (int i = 1; i<=n; i++)
    {
        for (int j = 0; j < m; j++) // sprawdzamy, czy istnieje krawędź, ale dla której nie zachodzi Obserwacja 1.
        {
            int u = E[j][0], v = E[j][1], waga = E[j][2];
            if (D[u]!=INF && D[u]+waga < D[v]) //jeżeli koszt dotarcia do poprzedniego wierzchołka (+7) jest mniejszy niż koszt dostanie się do aktualnego wierzchołka
            {
                D[v] = D[u]+waga;
 
                if (i==n) // jeżeli i dojdzie do n i wejdzie do tej pętli znaczy, że odkryliśmy cykl o ujemnej wadze
                {
                    printf("NIE");
                    return 0;
                }
            }
        }
    }
 
    //wypisywanie wyniku na ekran
    for (int i = 0; i < n; i++)
    {
        if (i!=s && D[i]<INF) printf("%d %d\n", i, D[i]);
    }
    return 0;
}
Osobiste