Algorithmen und Datenstrukturen · Senior · Frage 2 von 75
Welche zusätzliche Fähigkeit hat Bellman-Ford gegenüber Dijkstra?
- 1Er findet ganz nebenbei einen minimalen Spannbaum
- 2Er kann negative Gewichte und erkennt negative Zyklen
- 3Er läuft auf jedem Graphen schneller, in O(V + E)
Antwort zeigen
Richtige Antwort: Er kann negative Gewichte und erkennt negative Zyklen
Erklärung
Er relaxiert alle Kanten V - 1 Mal; verbessert ein V-ter Durchlauf noch eine Distanz, gibt es einen negativen Zyklus. Der Preis ist O(V × E), viel langsamer als Dijkstras O((V + E) log V).