Algorithmen und Datenstrukturen · Senior · Frage 1 von 75
Warum liefert Dijkstras Algorithmus mit negativen Kantengewichten falsche Ergebnisse?
- 1Negative Zahlen lassen sich gar nicht in einem binären Heap speichern
- 2Er läuft endlos, sobald ein Gewicht unter null liegt
- 3Ein abgeschlossener Knoten könnte über eine negative Kante noch kürzer werden
Antwort zeigen
Richtige Antwort: Ein abgeschlossener Knoten könnte über eine negative Kante noch kürzer werden
Erklärung
Dijkstra nimmt an, dass kein späterer Weg kürzer sein kann, sobald der nächste Knoten aus der Queue genommen ist. Eine negative Kante bricht diese Annahme. Bellman-Ford behandelt negative Gewichte in O(V × E) und erkennt auch negative Zyklen.