liefert in einem zusammenhängenden und bewerteten GraphenG mit einer Bewertung ϱ(k) > 0 für jede Kante k ∈ K(G) die kürzesten Wege von einer festen Ecke u ∈ E(G) aus zu allen übrigen Ecken des Graphen.

Dieser schöne und einfache Algorithmus von Dijkstra aus dem Jahre 1959 wurde zur gleichen Zeit unabhängig auch von Dantzig entdeckt. Er läßt sich wie folgt beschreiben.

Man bestimme zunächst eine Ecke y₁, die der Ecke u am nächsten ist. Wegen ϱ(k) > 0 ist y₁ natürlich eine zu u adjazente Ecke. Im zweiten Schritt bestimme man eine Ecke y₂, die der Ecke u am zweitnächsten ist. Eine solche Ecke ist dann adjazent zu u oder y₁. Im dritten Schritt bestimme man eine Ecke y₃, die der Ecke u am drittnächsten ist. Die Ecke y₃ ist dann adjazent zu u, y₁ oder y₂, usw.

Dieser Algorithmus, der für gerichtete Graphen mit positiver Bewertung völlig analog verläuft, besitzt die Komplexität O(|E(G)|²).