Tekst źródłowy strony 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
<math>O(|V||E|)</math>. 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 ==
{{kotwica|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 <math>G=(V,E)</math>
i funkcję wagową <math>w:E \to \mathcal{R}</math>. Algorytm
Bellmana-Forda wylicza dla zadanego wierzchołka <math>s</math>, czy
istnieje w grafie <math>G</math> cykl o ujemnej wadze osiągalny z
<math>s</math>. Jeżeli taki cykl nie istniej to algorytm oblicza
najkrótsze ścieżki z <math>s</math> do wszystkich pozostałych
wierzchołków wraz z ich wagami.

== Relaksacja ==

Podobnie ja to było w [[algorytm_dijkstry|Algorytmie Dijkstry]]
użyjemy metody relaksacji. Metoda ta polega na tym, że w trakcie
działania algorytmu dla każdego wierzchołka <math>v \in V</math>
utrzymujemy wartość <math>d(v)</math> będącą górnym ograniczeniem
wagi najkrótszej ścieżki ze <math>s</math> do <math>v</math>. W
algorytmie utrzymywać będziemy także dla każdego wierzchołka
<math>v</math> wskaźnik <math>\pi(v)</math> 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|algorytm_inicjalizacjia_sssp|
  INICJALIZUJ<math>(G,s)</math>
  '''for''' każdy wierzchołek <math>v\in V</math> '''do'''
    <math>d(v) = \infty</math>
    <math>\pi(v) = NIL</math>
  <math>d(s) = 0</math>
}}


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

relaksacja|Relaksacja]] krawędzi <math>(u,v)</math> polega na
sprawdzeniu, czy przechodząc krawędzią <math>(u,v)</math> z
<math>u</math> do <math>v</math>, nie otrzymamy krótszej ścieżki z
<math>s</math> do <math>v </math>niż ta dotychczas znaleziona.
Jeżeli tak to aktualizowane są także wartości <math>d(v)</math> i
<math>\pi(v)</math>. W celu relaksacji krawędzi <math>(u,v)</math>
używamy procedury