Witam,
mam pewne pytanie co do algorytmu Bellman-Forda(http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm). Czy w zależności od wybranego wierzchołka startowego w tym samym grafie, rezultat dla sprawdzenia ujemnych cykli może być inny? Przykładowy graf: http://edu.i-lo.tarnow.pl/inf/alg/001_search/images/0138a_01.gif
Bellman–Ford - ujemne cykle
- Rejestracja: dni
- Ostatnio: dni
- Postów: 137
0
- Rejestracja: dni
- Ostatnio: dni
- Lokalizacja: Kraków
- Postów: 1694
0
Co rozumiesz przez: "rezultat dla sprawdzenia ujemnych cykli może być inny?"? Algorytm ten ma za zadanie policzyć najkrótszą ścieżkę a jeśli istniej cykl ujemny to tego nie zrobi.
- Rejestracja: dni
- Ostatnio: dni
- Lokalizacja: Space: the final frontier
- Postów: 26433
2
@Kozy ten algorytm nie zwróci ci najkrótszych ściezek, bo przy ujemnym cyklu one zwyczajnie nie istnieją. Idea jest taka że ostatni obrót algorytmu nie powinien wprowadzić żadnej zmiany w relaksacji. Jeśli wprowadzi to znaczy że istnieje ujemny cykl i wyniki algorytmu są do kosza. Jedyna wyższość tego algorytmu nad Dijkstrą jest taka że wiesz czy wyniki mają sens czy też go nie mają.