Zaawansowane algorytmy i struktury danych/Wykład 5

From Studia Informatyczne

Spis treści

Abstrakt

Pierwsza część tego wykładu poświęcona będzie problemowi obliczania najkrótszych ścieżek w grafie z jednego źródła w przypadku, w którym wagi krawędzi mogą być ujemne. Zaprezentujemy algorytm Bellmana-Forda, który rozwiązuje ten problem w czasie O(|V||E|). W drugiej części zajmiemy się problemem obliczania odległości między wszystkimi parami wierzchołków. Pokażemy związki tego problemu z mnożeniem macierzy.

Definicja problemu

W wykładzie tym zajmiemy się problemem obliczania najkrótszych ścieżek w grafie wychodzących z jednego wierzchołka. Załóżmy, że mamy dany graf G = (V,E), funkcję w: E \to \mathcal{R} przypisującą wagi krawędziom oraz jeden wybrany wierzchołek s. Wagę ścieżki p=(v_0,v_1,\ldots,v_k) definiujemy jako wagę tworzących ją krawędzi:


w(p) = \sum_{i=0}^{k-1} w(v_{i}, v_{i+1}).


Odległość z wierzchołka u do wierzchołka v definiujemy jako

\delta(u,v) = \begin{cases} \min\{w(p): p \mbox{ ścieżka z } u \mbox{ do } v\}, & \mbox{jeżeli istnieje ścieżka z } u \mbox{ do } v,\\ \infty & \mbox{w przeciwnym przypadku.} \end{cases}

Najkrótszą ścieżką z wierzchołka u do wierzchołka v jest każda ścieżka p z u do v, której waga w(p) jest równa odległości \delta(u,v) z u do v.

W problemie najkrótszych ścieżek z jednego wierzchołka chcemy obliczyć odległości \delta(s,v) dla wszystkich wierzchołków v\in V wraz z drzewem najkrótszych ścieżek z s. Drzewem najkrótszych ścieżek o korzeniu w s nazywamy podgraf skierowany G' = (V', E'), w którym V' \subseteq V, E' \subseteq E taki, że:

  • V' jest zbiorem wierzchołków w G do których istnieje ścieżka z s,
  • G' jest drzewem którego korzeniem jest s,
  • dla każdego wierzchołka v\in V' jedyna ścieżka z s do v w grafie G' jest najkrótszą ścieżką z s do v w grafie G.

W naszych algorytmach drzewo najkrótszych ścieżek będziemy reprezentować jako funkcję poprzedników \pi:V \to V, określającą poprzednika wierzchołka v w drzewie najkrótszych ścieżek. Drzewo najkrótszych ścieżek G_{\pi}=(V_{\pi},E_{\pi}) możemy uzyskać z \pi w następujący sposób:

V_{\pi} = \{v \in V : \pi(v) \neq NIL\} \cup \{s\},
E_{\pi} = \{(\pi(v),v) \in E: v \in V_{\pi} - \{s\}\}.

Algorytm Bellmana-Forda

Algorytm Bellmana-Forda służy do rozwiązania problemu znalezienia najkrótszych ścieżek w grafie, w którym wagi krawędzi mogą być ujemne. W problemie tym mamy dany graf G=(V,E) i funkcję wagową w:E \to \mathcal{R}. Algorytm Bellmana-Forda wylicza dla zadanego wierzchołka s, czy istnieje w grafie G cykl o ujemnej wadze osiągalny z s. Jeżeli taki cykl nie istnieje, algorytm oblicza najkrótsze ścieżki z s do wszystkich pozostałych wierzchołków wraz z ich wagami.

Relaksacja

Podobnie jak to było w Algorytmie Dijkstry, użyjemy metody relaksacji. W metodzie tej utrzymujemy dla każdego wierzchołka v \in V wartość d(v), będącą górnym ograniczeniem wagi najkrótszej ścieżki z s do v. W algorytmie utrzymywać będziemy także dla każdego wierzchołka v wskaźnik \pi(v) wskazujący na poprzedni wierzchołek, przez który prowadzi dotychczas znaleziona najkrótsza ścieżka. Na początku wielkości te inicjujemy przy pomocy następującej procedury:


Algorytm Inicjacja algorytmu najkrótszych ścieżek


 INICJACJA(G,s)
 1  for każdy wierzchołek v\in V do
 2  begin
 3    d(v) = \infty
 4    \pi(v) = NIL
 5  end
 6  d(s) = 0
 7  return (d,\pi)


Ustalone przez tą procedurę wartości d(v) są dobrymi ograniczeniami górnymi na odległości w grafie.

Relaksacja krawędzi (u,v) polega na sprawdzeniu, czy przechodząc krawędzią (u,v) z u do v, nie otrzymamy krótszej ścieżki z s do v niż ta dotychczas znaleziona. Jeżeli tak, to aktualizowane są także wartości d(v) i \pi(v). W celu relaksacji krawędzi (u,v) używamy następującej procedury nazwanej tutaj RELAKSUJ.

Algorytm Relaksacja krawędzi


 RELAKSUJ(u,v,w,d,\pi)
 1  if d(v) > d(u) + w(u,v) then
 3  begin
 4    d(v) = d(u) + w(u,v)
 5    \pi(v) = u
 6  end

Algorytm

Po przypomnieniu czym była relaksacja, gotowi jesteśmy na zapisanie algorytmu Bellmana-Forda, a następnie udowodnienie jego poprawności.

Algorytm Bellmana-Forda


 BELLMAN-FORD(G,w,s)
 1  (d,\pi)=INICJUJ(G,s)
 2  for i=1 to |V|-1 do
 3    for każda krawędź (u,v) \in E do
 4      RELAKSUJ(u,v,w,d,\pi)
 5  for każda krawędź (u,v) \in E do
 6    if 'd(v)>d(u) + w(u,v) then
 7      return NIL
 8  return (d,\pi)
Poniższa animacja przedstawia działanie algorytmu dla grafu o pięciu wierzchołkach.


Algorytm ten działa w czasie O(|V||E|), co łatwo pokazać, gdyż:

  • proces inicjacji w linii 1 zajmuje czas O(|V|),
  • w każdym z |V| przebiegów głównej pętli w linii 2 algorytmu przeglądane są wszystkie krawędzie grafu w linii 3 , co zajmuje czas O(|V||E|),
  • końcowa pętla algorytmu w liniach 5-7 działa w czasie O(|E|).

Poprawność

Dowód poprawności algorytmu Bellmana-Forda zaczniemy od pokazania, że algorytm działa poprawnie przy założeniu, że w grafie nie ma cykli o ujemnych wagach.

Lemat 1

Niech G = (V,E) będzie grafem skierowanym i niech funkcja w:E \to \mathcal{R} zadaje wagi krawędzi. Niech s będzie wierzchołkiem, z którego liczymy odległości algorytmem Bellmana-Forda. Jeżeli w grafie nie ma cykli o ujemnej wadze osiągalnych z s, to algorytm poprawnie oblicza odległości, tzn. na koniec działania algorytmu dla każdego v \in V wartość d(v) jest odległością w G z s do v.

Dowód

Oznaczmy przez \delta(v,u) odległość z wierzchołka v do u w grafie G. Niech v będzie wierzchołkiem osiągalnym ze źródła s i niech p = (v_0, v_1, \ldots, v_k) oznacza najkrótszą ścieżkę z s do v, gdzie v_0 = s oraz v_k = v. Ścieżka ta jest ścieżką prostą, bo najkrótsze ścieżki muszą być proste, więc k\le |V|-1. Pokażemy teraz indukcyjnie, że poczynając od i-tego przebiegu zachodzi d(v_i) = \delta(s,v_i) dla i = 0,1,\ldots, k. W algorytmie wykonujemy |V|-1 obrotów pętli oraz k \le |V|-1, co oznacza, że z tej tezy indukcyjnej wynika poprawność algorytmu.

Zauważmy, że teza indukcyjna zachodzi po inicjacji algorytmu, gdyż d(v_0) = d(s) = 0 i \delta(s,s) = \delta(s,v_0). Załóżmy, że teza indukcyjna zachodzi dla kroku k-tego. Ponieważ ścieżki p = (v_0, v_1, \ldots, v_i) dla i \le k są najkrótsze jako podścieżki ścieżki p, to po k+1 wykonaniu pętli wartości d(v_i) dla i \le k się nie zmienią. Pozostaje nam więc do pokazania to, że wartość d(v_{k+1}) będzie dobrze policzona. W k+1 przebiegu wykonujemy między innymi relaksację krawędzi (v_{k}, v_{k+1}). Ponieważ d(v_k) jest dobrze policzone, po tej relaksacji wyznaczona będzie także poprawnie wartość d(v_{k+1}), bo założyliśmy, że najkrótsza ścieżka do v_{k+1} przechodzi przez v_k.

Pozostaje nam jedynie zastanowić się, co się dzieje, gdy wierzchołek v nie jest osiągalny z s. Musi wtedy zachodzić d(v) = \infty pod koniec działania algorytmu. Gdyby tak nie było, oznaczałoby to, z właściwości procedury RELAKSUJ, że istnieje ścieżka od s do v, co daje sprzeczność. image:End_of_proof.gif

Twierdzenie 2

Niech G = (V,E) będzie grafem skierowanym i niech funkcja w:E \to \mathcal{R} zadaje wagi krawędzi. Załóżmy, że algorytm Bellmana-Forda został wykonany dla wierzchołka s. Jeżeli graf zawiera cykl o ujemnej wadze osiągalny ze źródła s, to algorytm zwraca wartość NIL, w przeciwnym wypadku d(v) jest odległością z s do v, a \pi(v) wyznacza drzewo najkrótszych ścieżek o korzeniu w s.


Dowód

Załóżmy najpierw, że graf nie zawiera cykli o ujemnej wadze, które byłyby osiągalne z s. Wtedy z Lematu 1 wiemy, że d(v) są poprawnie policzonymi odległościami. Jeżeli odległości d(v) zostały poprawnie policzone przez funkcję RELAKSUJ, to \pi(v) koduje najkrótsze ścieżki w grafie. Wynika to z właściwości funkcji RELAKSUJ, która wyliczając odległość wyznacza jednocześnie, przez jaki wierzchołek prowadzi ta najkrótsza ścieżka.

Musimy teraz pokazać, że algorytm poprawnie wykrywa, czy w grafie G istnieje cykl ujemnej długości osiągalny z s. Jeżeli nie ma takiego cyklu, wtedy d(v) są poprawnie policzone przed wykonaniem testu w liniach 5-8 algorytmu Bellmana-Forda. W takim razie zachodzi:


d(v) = \delta(s,v) \le \delta(s,u) + w(u,v) = d(u) + w(u,v).


Powyższa nierówność zachodzi, ponieważ s \to u \to v jest ścieżką w grafie, a więc jest nie krótsza niż najkrótsza ścieżka s \to v. Widzimy więc, że w tym przypadku żaden z testów w linijce 6 algorytmu nie będzie spełniony i algorytm nie zwróci NIL.

Załóżmy teraz, że w grafie G istnieje cykl o ujemnej wadze osiągalny z s. Oznaczmy ten cykl jako c =(v_0, v_1,\ldots, v_k), gdzie v_0 = v_k. Dla cyklu tego mamy:

\sum_{i=0}^{k-1} w(v_{i},v_{i+1}) <0.      (1)

Gdyby w tej sytuacji algorytm Bellmana-Forda nie zwrócił wartości NIL, to dla każdej krawędzi (v_i, v_{i+1}) musiałaby zachodzić nierówność d(v_{i}) + w(v_i, v_{i+1}) \ge d(v_{i+1}). Sumując tę nierówność stronami po wszystkich i = 0,\ldots, k-1, otrzymujemy:


\sum_{i=0}^{k-1} \left[d(v_i) + w(v_i, v_{i+1})\right] \ge \sum_{i=0}^{k-1} d(v_{i+1}),
\sum_{i=0}^{k-1} d(v_i) + \sum_{i=0}^{k-1} w(v_i, v_{i+1}) \ge \sum_{i=1}^{k} d(v_{i}),


ponieważ v_0 = v_k to


\sum_{i=0}^{k-1} d(v_i) + \sum_{i=0}^{k-1} w(v_i, v_{i+1}) \ge \sum_{i=0}^{k-1} d(v_{i}).


Wiemy, że cykl c jest osiągalny z s, a zatem dla każdego i = 0,\ldots,k mamy d(v)<\infty. Możemy więc skrócić \sum_{i=0}^{k-1} d(v_i) po obydwu stronach nierówności otrzymując:


\sum_{i=0}^{k-1} w(v_i, v_{i+1}) \ge 0,


co stoi w sprzeczności z nierównością (1). Jeżeli więc w grafie istnieje cykl o ujemnej wadze osiągalny z s, to algorytm zwróci NIL. image:End_of_proof.gif