Algorithmen und Datenstrukturen · Middle · Frage 58 von 75
Was berechnet Dijkstras Algorithmus?
- 1Kürzeste Wege von einem Knoten, wenn die Gewichte nicht negativ sind
- 2Den minimalen Spannbaum eines gewichteten Graphen
- 3Kürzeste Wege in jedem Graphen, auch mit negativen Gewichten
Antwort zeigen
Richtige Antwort: Kürzeste Wege von einem Knoten, wenn die Gewichte nicht negativ sind
Erklärung
Er nimmt wiederholt den unbesuchten Knoten mit der kleinsten bekannten Distanz (aus einer Priority Queue) und relaxiert seine Kanten. Mit binärem Heap läuft er in O((V + E) log V). Negative Gewichte brechen ihn.