Bellman–Ford - ujemne cykle

0

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

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.

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

1 użytkowników online, w tym zalogowanych: 0, gości: 1