Najkrótsze ścieżki dopuszczając ujemne wagi krawędzi

by Jerry Sky



Wspomniany na wcześniejszym wykładzie algorytm Dijkstry pozwala na wyznaczenie najkrótszych ścieżek od startowego wierzchołka do wszystkich innych wierzchołków w grafie G=(V,E,l)G = (V,E,l), w przypadku gdzie wagi krawędzi są dodatnie (l:ER+l: E\to \mathbb{R}_+). Teraz będziemy rozważać grafy, gdzie mamy również ujemne wagi krawędzi (l:ERl: E \to \mathbb{R}).

Dijkstra’s algorithm

W algorytmie Dijkstry wykorzystywany był następujący fakt:
najkrótsza ścieżka od wierzchołka startowego ss do wierzchołka vv może przechodzić tylko przez wierzchołki będące w mniejszej odległości od ss nie wierzchołek vv.
Własność ta nie jest prawdziwa jeśli dopuścimy ujemne wagi krawędzi grafu:

negative example with Dijkstra

Zauważmy, że algorytm Dijkstry wykonuje pewną sekwencję procedur update((u,v)E)((u,v) \in E):

  1. v.dist=min{v.dist,u.dist+l(u,v)}v.\mathrm{dist} = \min \{ v.\mathrm{dist}, u.\mathrm{dist} + l(u,v) \}

Procedura update ma następujące własności:

Widzimy zatem, że wykonując dowolną sekwencję procedur update wartości v.distv.\mathrm{dist} dla każdego wierzchołka vVv \in V przyjmuje wartość większą lub równą prawdziwej najkrótszej odległości od wierzchołka startowego ss.

Na poprzedniej ilustracji widzieliśmy przykład grafu, dla którego sekwencja wykonań procedur update wykonywana przez algorytm Dijkstry nie pozwoli wyznaczyć prawidłowej najkrótszej ścieżki od wierzchołka SS do AA. Zastanówmy się jakie własności musi mieć najkrótsza ścieżka od wierzchołka ss do vv (powiedzmy, że będzie ona wyglądać następująco su1u2ukvs \to u_1 \to u_2 \to \dotsb \to u_k \to v) oraz sekwencja procedur update pozwalająca ją wyznaczyć:

Algorytm Bellmana-Forda

W celu uniknięcia zastanawiania się czy wykonamy procedurę update w odpowiedniej kolejności możemy wykonać ją dla każdej krawędzi w grafie V1|V| - 1 razy. Zauważmy jednak, że w przypadku wielu grafów ścieżki będą miały mnie krawędzi niż V1|V| - 1, czyli mniejsza liczba (niż V1|V| - 1) powtórzeń procedury update dla każdego wierzchołka wystarczy aby wyznaczyć najkrótsze ścieżki. Zauważmy, że jeśli wykonamy procedurę update dla każdej krawędzi w grafie, ale nie zmodyfikujemy żadnej ścieżki to dalsze wykonywanie procedury update już nic nie zmieni.

Bellman-Ford(G,s)(G,s):

  1. for all vVv \in V:
    1. v.distv.\mathrm{dist} \gets \infty
    2. v.prevv.\mathrm{prev} \gets null
  2. s.dist0s.\mathrm{dist} \gets 0
  3. s.prevss.\mathrm{prev} \gets s
  4. repeat until change=True\mathrm{change} = True:
    1. changeFalse\mathrm{change} \gets False
    2. for all (u,v)E(u,v) \in E:
      1. if v.dist>u.dist+l(u,v)v.\mathrm{dist} > u.\mathrm{dist} + l(u,v)
        1. v.dist=u.dist+l(u,v)v.\mathrm{dist} = u.\mathrm{dist} + l(u,v)
        2. v.prev=uv.\mathrm{prev} = u
        3. change=True\mathrm{change} = True

Złożoność obliczeniowa: wewnętrzna pętla ma złożoność obliczeniową O(E)O(|E|) i jest wykonywana co najwyżej O(V)O(|V|) razy co daje złożoność obliczeniową całego algorytmu O(EV)O(|E| \cdot |V|).

Przykład (Algorytm Bellmana-Forda)

example bellman ford

Zauważmy, że jeśli w grafie istnieje ujemny cykl (tzn. suma wag krawędzi w cyklu jest ujemna) to przechodzenie w kolejne razy tego ujemnego cyklu będzie zmniejszać długość ścieżek w grafie. W takim przypadku zakładamy, że najkrótsza ścieżka nie istnieje. Aby sprawdzić, czy graf posiada ujemny cykl wystarczy powtórzyć wykonanie procedury update dla każdej krawędzi V|V| razy. Jeśli w ostatniej rundzie wykonywania procedury update któraś wartość v.distv.\mathrm{dist} ulegnie zmianie to wiemy, że w grafie mamy ujemny cykl (ponieważ jak wcześniej zauważyliśmy najkrótsza ścieżka może mieć co najwyżej V1|V| - 1 krawędzi).

More