Algorytmy i struktury danych · Senior · Pytanie 1 z 75
Dlaczego algorytm Dijkstry daje błędne wyniki przy ujemnych wagach krawędzi?
- 1Liczb ujemnych w ogóle nie da się trzymać w kopcu binarnym
- 2Zapętla się, gdy tylko jakakolwiek waga jest poniżej zera
- ✓Poprawna odpowiedź: Zamknięty wierzchołek wciąż może się skrócić przez ujemną krawędź
Wyjaśnienie
Dijkstra zakłada, że gdy najbliższy wierzchołek zostanie wyjęty z kolejki, żadna późniejsza ścieżka nie będzie krótsza. Ujemna krawędź łamie to założenie. Bellman-Ford obsługuje ujemne wagi w O(V × E) i dodatkowo wykrywa ujemne cykle.