Zaawansowane algorytmy i struktury danych/Wykład 5

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.

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 {ℛ}$. 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 istniej to algorytm oblicza najkrótsze ścieżki z $s$ do wszystkich pozostałych wierzchołków wraz z ich wagami.

Relaksacja

Podobnie ja to było w Algorytmie Dijkstry użyjemy metody relaksacji. Metoda ta polega na tym, że w trakcie działania algorytmu dla każdego wierzchołka $v\in V$ utrzymujemy wartość $d(v)$ będącą górnym ograniczeniem wagi najkrótszej ścieżki ze $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 Inicjalizacja algorytmu najkrótszych ścieżek

---

 INICJALIZUJ$(G,s)$
 for każdy wierzchołek $v\in V$ do
   $d(v)=\mathrm{\infty }$
   $\pi (v)=NIL$
 $d(s)=0$

Ustalone przez tą procedure wartości $d(v)$ są dobrymi ograniczeniami górnymi na odległości.

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 procedury RELAKSUJ.

Algorytm Relaksacja krawędzi

---

 RELAKSUJ$(u,v,w)$
 if d(v) > d(u) + w(u,v) then
   d(v) = d(u) + w(u,v)
   \pi(v) = u

Algorytm

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