Wählt man eine ganze Menge S von Knoten als Startknoten und einen ganze Menge E von Knoten als Endknoten, so berechnet der Algorithmus von Dijkstra einen kürzesten Pfad, der einen Knoten aus S mit einem Knoten aus E verbindet. Der Algorithmus muss dann so abgewandelt werden, dass zu Beginn alle Startknoten in T aufgenommen und mit 0 nummeriert werden und die Schleife abgebrochen wird, sobald ein Knoten aus E erreicht, also in T eingefügt wurde.

Ändert man die Abbruchbedingung dahin, dass erst nach erreichen aller Knoten die Schleife verlassen wird, so berechnet der Algorithmus einen minimal spannenden Baum in G, mit der Eigenschaft, dass schnell von allen Knoten die kürzesten Pfade zum Startknoten s gefunden werden können (in dem man den letzten Schritt für den Knoten ausführt).

Vergleich mit Prim

Der Algorithmus von Dijkstra ähnelt dem Algorithmus von Prim. Letzterer dient der Berechnung eines minimal spannenden Baumes. Statt s kann Prim den Startknoten beliebig wählen. Die Schleife wird abgebrochen, wenn alle Knoten erreicht wurden. Da es nur auf die Berechnung eines minimal spannenden Baumes ankommt, und nicht auf die kürzesten Pfade zu s, ist einen Nummerierung der Knoten bei Prim nicht notwendig. Ansonsten sind die Algorithmen von Dijkstra und Prim identisch.

Optimalitätsprinzip

Der Algorithmus stützt sich auf das Optimalitätsprinzip, welches besagt, dass wenn der kürzeste Pfad von A nach C über B führt, der Teilpfad A B auch der kürzeste Pfad von A nach B sein muss.

Effiziente Implementierung

Das Grundprinzip des Algorithmus ist relativ einfach. Die effiziente Bestimmung des nächsten Knotens ist aber aufwändig zu implementieren. Man benötigt als Datenstruktur so genannte Fibonacci-Heaps. Die Laufzeit beträgt O(m + n * log(n)), wobei m die Zahl der Kanten und n die Zahl der Knoten ist.

Beispiele: Floyd-Warshall-Algorithmus, Bellman-Ford-Algorithmus