Time and Space Complexity
Lektion 7 von 9 im Kurs Dijkstra-Algorithmus - Graph-Algorithmen von Coddy.
Zeitkomplexität:
- O(V2 + V*E) wie hier geschrieben (jede der V Runden scannt Knoten, um das Minimum zu finden, und scannt die Kanten zum Relaxieren). Mit einem binären Heap und einer Adjazenzliste verbessert sie sich auf O((V + E) log V).
Platzkomplexität:
- O(V) für die distance- und visited-Arrays (plus die Eingabekanten).
Zusammenfassung:
- Dijkstra findet kürzeste Wege von einer einzelnen Quelle für nicht-negative Gewichte, indem er gierig den nächstgelegenen Knoten finalisiert und dessen Kanten relaxiert.
- Er funktioniert nicht mit negativen Kanten; verwenden Sie Bellman-Ford für diese.
Probier es selbst
Diese Lektion enthält keine Programmieraufgabe.
Teste dich selbstDiese Lektion enthält ein kurzes Quiz. Starte die Lektion, um es zu beantworten und deinen Fortschritt zu speichern.
Alle Lektionen in Dijkstra-Algorithmus - Graph-Algorithmen
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity