Algorithmen und Datenstrukturen · Senior · Frage 66 von 75
Was ist der Hauptvorteil von Dijkstra mit Fibonacci-Heap gegenüber einem binären Heap?
- 1Amortisiertes O(1) für Decrease-Key: O(E + V log V)
- 2Er braucht überhaupt keine Priority Queue
- 3Er funktioniert auch mit negativen Gewichten korrekt
Antwort zeigen
Richtige Antwort: Amortisiertes O(1) für Decrease-Key: O(E + V log V)
Erklärung
Bei dichten Graphen schlägt das O((V + E) log V). In der Praxis sind binäre Heaps (oft mit Lazy Deletion statt Decrease-Key) meist schneller, weil Fibonacci-Heaps große Konstanten haben.