markiere alle Knoten als vorläufig ;
markiere den Startknoten (A) als 0; (endgültig)
REPEAT
Sei x der zuletzt endgültig markierte Knoten;
modifiziere alle Nachbarn y von x durch
m(y) := min{m(y),m(x)+c(x,y)};
markiere den Knoten mit der kleinsten vorläufigen
Markierung als endgültig;
UNTIL alle Knoten sind markiert
Die Laufzeit des Dijkstra-Algorithmus liegt in O(|V|2) , was bei dicht besetzten Graphen eine erhebliche Verbesserung des ersten generischen Algorithmus bedeutet.
Allerdings ist auch beim Dijkstra-Algorithmus auf stets positive Kantenkosten zu achten, da der Algorithmus sonst nicht korrekte kürzeste Wege berechnet. Bei negativen Kantenkosten wären nämlich auch negative Zyklen möglich, die die Wohldefiniertheit des kürzesten Wege Problems verletzen würden.