Wie ganz zu Beginn des Teils zu Graphen bemerkt, sind Graphenalgorithmen besonders leistungsfähig, d.h. der Rechenaufwand um Probleme zu lösen ist gering und steigt nur mäßig mit zunehmender Problemgröße.

Vorgehen beim Ermitteln der Komplexität

Es wird analysiert, wie viele Elementaroperationen, wie zum Beispiel Additionen oder Vergleiche von Zahlen bei Anwendung eines Algorithmus in Abhängigkeit von der Problemgröße m durchgeführt werden. Allerdings interessiert nicht, wie viele Operationen es genau sind, sondern nur die Größenordnung. Ist die genaue Zahl der Elementaroperationen in einem Algorithmus zum Beispiel 7m³+5m²-2m+124, würde man nur auf die höchste Potenz schauen und die Komplexität mit O(m³) angeben.

Komplexität des Dijkstra-Algorithmus

Die Anzahl der Knoten im Graphen wird im Folgenden mit m bezeichnet.

• Jeder Knoten kann maximal einmal Arbeitsknoten sein, d.h. es gibt maximal m Iterationen
• In jeder Iteration muss der Arbeitsknoten unter m Knoten gefunden werden. Zudem müssen bei der Aktualisierung der vorläufigen Markierung die Werte von im schlimmsten Fall m-1 benachbarten Knoten verglichen und ggf. aktualisiert werden. Diese beiden Schritte erfolgen hintereinander, d.h. der Aufwand innerhalb einer Iteration steigt linear mit der Anzahl der Knoten im Problem.

In Abhängig von der Größe des Problems steigt damit die Anzahl der auszuführenden Elementaroperationen im Quadrat, d.h. die Komplexität beträgt O(m²). Es handelt sich dabei wie immer um eine Betrachtung des schlimmsten Falls, in vielen praktischen Anwendungsfällen wird sich der Algorithmus sogar noch einmal günstiger verhalten.