Zaawansowane algorytmy i struktury danych/Wykład 5

Z Studia Informatyczne
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


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