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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 8: Linia 8:
 
obliczania odległości między wszystkimi parami wierzchołków.
 
obliczania odległości między wszystkimi parami wierzchołków.
 
Pokażemy związki tego problemu z mnożeniem macierzy.
 
Pokażemy związki tego problemu z mnożeniem macierzy.
 +
  
 
== Algorytm Bellmana-Forda ==
 
== Algorytm Bellmana-Forda ==
Linia 23: Linia 24:
 
wierzchołków wraz z ich wagami.
 
wierzchołków wraz z ich wagami.
  
== Relaksacja ==
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
+
=== Relaksacja ===  
 +
<div class="mw-collapsible-content" style="display:none">
 
Podobnie ja to było w [[algorytm_dijkstry|Algorytmie Dijkstry]]
 
Podobnie ja to było w [[algorytm_dijkstry|Algorytmie Dijkstry]]
 
użyjemy metody relaksacji. Metoda ta polega na tym, że w trakcie
 
użyjemy metody relaksacji. Metoda ta polega na tym, że w trakcie
Linia 57: Linia 59:
 
Jeżeli tak to aktualizowane są także wartości <math>d(v)</math> i
 
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>
 
<math>\pi(v)</math>. W celu relaksacji krawędzi <math>(u,v)</math>
używamy procedury
+
używamy procedury RELAKSUJ.
 +
 
 +
{{algorytm|Relaksacja krawędzi|algorytm_relaksacja_krawędzi|
 +
  RELAKSUJ<math>(u,v,w)</math>
 +
  '''if''' d(v) > d(u) + w(u,v) '''then'''
 +
    d(v) = d(u) + w(u,v)
 +
    \pi(v) = u
 +
}}
 +
</div>
 +
</div>

Wersja z 20:55, 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