Bellman Ford

Rafał Nowak
rnowakrnowak

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

ShortestPaths.png

Aby znaleźć najkrótszą ścieżkę do wierzchołka 2, należy rozpocząć przeglądanie od wierzchołka 2, chodząc wstecz po krawędziach pomarańczowych, aż do napotkania wierzchołka źródłowego $s$.
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

(1)
\begin{align} s \to u_1 \to u_2 \to \ldots \to u_k \end{align}

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

(2)
\begin{align} s \to u_1 \to u_2 \to \ldots \to u_j \qquad (j<k) \end{align}

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 dopuszczalne są 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 określić 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 $s$ do wierzchołka $u$.


Najpierw zajmiemy się wyznaczeniem wartości $D[u]$ dla każdego wierzchołka $u\in V$.

Algorytm opiera się na bardzo prostej obserwacji:

Obserwacja 1
Dla każdej krawędzi $u \to v$, zachodzi nierówność
(3)
\begin{align} D[u] + f(u \to v) \geq D[v] \end{align}

Jej interpretacja jest oczywista. Mianowicie, najkrótsza droga do wierzchołka $v$ nie może być dłuższa niż przejście najkrótszą drogą do wierzchołka $u$, a następnie krawędzią $u \to v$.
Można także udowodnić twierdzenie odwrotne, tzn. jeśli nierówność 3 zachodzi dla każdej krawędzi $u\to v\in E$, to funkcja $D[..]$ jest prawidłową funkcją odległości od źródła $s$.

Teraz możemy przystąpić do zapisania wstępnej wersji algorytmu Bellmana-Forda:

  1. Dla każdego wierzchołka $u \in V$, wykonaj $D[u] := \infty$
  2. $D[s] := 0$
  3. Dopóki istnieje krawędź $u\to v$, dla której $D[u]+f(u \to v) < D[v]$, wykonaj
    1. $D[v] := D[u]+f(u\to v)$

Analiza algorytmu

Na pierwszy rzut oka, właściwie nie widać dlaczego podany algorytm miałby w ogóle się zakończyć. Skąd niby wiemy, że krok 3, nie będzie wykonywał się w nieskończoność. Dowód tego faktu wymagałby wprowadzenia pojęcia drzewa najkrótszych ścieżek, które trochę po cichu przedstawiliśmy na rysunku 2.
Można bowiem udowodnić że wykonanie jednej iteracji, tj. kroku 3 sprawia, że co najmniej jeden wierzchołek $u$ ma prawidłowo obliczoną wartość $D[u]$. Kolejne wykonanie kroku 3, sprawi, że co najmniej dwa wierzchołki mają prawidłowo obliczoną długość najkrótszej ścieżki od źródła $s$, itd.
Stąd, jeśli w grafie mamy $n$ wierzchołków, w powyższym algorytmie, krok 3 należy wykonać co najwyżej $n-1$ razy.

Złożoność czasowa i pamięciowa

Niech $n$ i $m$ oznaczają odpowiednio liczbę wierzchołków i krawędzi w grafie $G$.
Ponieważ wykonanie kroku 3 wymaga sprawdzenia pewnego warunku dla każdej krawędzi w grafie, więc całkowita złożoność czasowa algorytmu Bellmana-Forda jest rzędu $\mathcal{O}(n\cdot m)$.
Jeśli chodzi o złożoność pamięciową, to w algorytmie tym nie jest wymaga żadna dodatkowa struktura danych. Często nawet implementuje się ten algorytm w taki sposób, że nie pamiętana jest nawet lista sąsiedztwa w grafie. Jedyne, co jest potrzebne, to umiejętność przeglądania wszystkich krawędzi. Poniższa implementacja w języku C++ zapamiętuje wszystkie krawędzie w wektorze z biblioteki STL.

Znajdowanie cykli ujemnych w grafie

Pomińmy teraz założenie o braku ujemnych cykli w grafie. Przypuśćmy, że chcemy sprawdzić istnienie takiego cyklu.
Okazuje się, że powyższa analiza algorytmu Bellmana-Forda bardzo szybko daje odpowiedź na ten problem.
Powiedzieliśmy bowiem, że krok 3 w algorytmie Bellmana-Forda może wykonywać się co najwyżej $n-1$ razy. Gdybyśmy bowiem zaś spróbowali wykonać ten krok po raz $n$-ty, to warunek, sprawdzany w tym kroku, na pewno nie będzie spełniony.
Okazuje się, że jeśli w danym grafie istnieje ujemny cykl, to powyższy algorytm nigdy się nie zakończy, tj. krok 3, zawsze będzie poprawiał pewną wartość $D[v]$. Prawdziwe jest również twierdzenie odwrotne.
Podsumowując, jeśli krok 3 wykona się po raz $n$-ty, to oznacza to, że wykryliśmy w grafie ujemny cykl.
Poniższa implementacja zawiera wykrywanie właśnie tego typu sytuacji.

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;
}

Ćwiczenia

źródło: Algorytmika praktyczna. Nie tylko dla mistrzów. Piotr Stańczak, PWN Warszawa (2009)

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License