Zaawansowane algorytmy i struktury danych/Wykład 5

Z Studia Informatyczne
< Zaawansowane algorytmy i struktury danych
Wersja z dnia 20:48, 19 lip 2006 autorstwa Sank (dyskusja | edycje)
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
Przejdź do nawigacjiPrzejdź do wyszukiwania

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

{{{2}}}


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 i funkcję wagową . Algorytm Bellmana-Forda wylicza dla zadanego wierzchołka , czy istnieje w grafie cykl o ujemnej wadze osiągalny z . Jeżeli taki cykl nie istniej to algorytm oblicza najkrótsze ścieżki z 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 utrzymujemy wartość będącą górnym ograniczeniem wagi najkrótszej ścieżki ze do . W algorytmie utrzymywać będziemy także dla każdego wierzchołka wskaźnik 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
 for każdy wierzchołek  do
   
   
 


Ustalone przez tą procedure wartości są dobrymi ograniczeniami górnymi na odległości.

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