Routenplaner sind ein prominentes Beispiel, bei der dieser Algorithmus eingesetzt werden kann. Der Graph repräsentiert hier das Straßennetz, welches verschiedene Punkte miteinander verbindet. Gesucht ist die kürzeste Route zwischen zwei Punkten.

Dijkstras Algorithmus wird auch im Internet als Routing-Algorithmus in OSPF eingesetzt.

Implementation

• Setze i = 0;
• Setze s als Startgraph T und nummeriere s mit i (= 0);
• Solange T noch nicht e enthält,
  • Erhöhe i um 1;
  • suche eine Kante minimalen Gewichts, die einen Knoten, der nicht in T ist, mit T verbindet und
  • füge diese Kante und den damit verbundenen Knoten v zu T hinzu;
  • Nummeriere v mit i;
• Laufe von e beginnend zurück zu s, indem als nächster Knoten immer der Knoten mit kleinster Nummerierung gewählt wird;

Der im letzten Schritt durchlaufene Pfad, stellt einen kürzesten Pfad zwischen e und s dar.

Berechnung des Abstandes

Will man den Abstand der Knoten s und e berechnen, so braucht man beim Zurücklaufen im letzten Schritt einfach nur die Kantengewichte der entlanggelaufenen Kanten zu addieren.