Zur Lösung des kürzesten-Wege-Problems könnte man versuchen, alle Wege vom Startknoten s zum Zielknoten t zu durchlaufen und den kürzesten auszuwählen.

Das folgende Beispiel soll illustrieren, dass dieses Vorgehen viel zu langwierig ist

In diesem Graphen mit 2 + 2*4 Knoten gibt es 2⁴ Wege s nach t.

Verallgemeinert man dieses Bild auf einen Graphen mit 2 + 2*100 Knoten, so hat dieser bereits 2¹⁰⁰ und damit ungefähr 10³⁰ Wege. Die Anzahl der Wege kann somit exponentiell in der Anzahl der Knoten wachsen, so dass eine Auflistung aller Wege selbst auf sehr schnellen Rechnern zu viel Zeit in Anspruch nehmen wird.

Das im folgenden beschriebene Verfahren von Dijkstra wird uns erlauben, kürzeste Wege effizient zu berechnen.

---