Abschätzung der Laufzeit
Lemma 3
Die Laufzeit des Dijkstra-Algorithmus ist
Beweis:
O(n (Max {O(finde Min), O(lösche Min), O(füge ein)}
+ m O(verringere))
-
Die while-Schleife kann höchstens n = |V| mal ausgeführt werden,
da jeder Knoten höchstens einmal als Minimum auftreten kann.
Die darin enthaltene for-Schleife kann aber auch nur einmal für
jede Kante durchlaufen werden. Somit:
- n Ausführungen von finde Min, lösche Min, füge ein,
- m Ausführungen von verringere.
 |
 |
 |