Algorytmy i struktury danych · Senior · Pytanie 2 z 75
Jaką dodatkową możliwość ma Bellman-Ford w porównaniu z Dijkstrą?
- 1Przy okazji znajduje minimalne drzewo rozpinające
- ✓Poprawna odpowiedź: Działa z ujemnymi wagami i wykrywa ujemne cykle
- 3Działa szybciej na każdym grafie, w O(V + E)
Wyjaśnienie
Relaksuje wszystkie krawędzie V - 1 razy; jeśli V-te przejście wciąż poprawia odległość, istnieje ujemny cykl. Ceną jest O(V × E), dużo wolniej niż O((V + E) log V) u Dijkstry.