Zaawansowane algorytmy i struktury danych/Wykład 5: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
Linia 10: Linia 10:
  
 
== Algorytm Bellmana-Forda ==
 
== Algorytm Bellmana-Forda ==
{{kotwica|algorytm_bellmana-forda}}
+
{{kotwica|algorytm_bellmana-forda|}}
  
  

Wersja z 20:49, 19 lip 2006

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


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