Ein Navi findet in wenigen Sekunden die kürzeste Verbindung zwischen zwei Punkten. Wie macht es das?

Im Navi sind alle erreichbaren Orte als Knoten und die Wege zwischen ihnen als Kanten dargestellt. Die Kanten sind jeweils mit der Weglänge gewichtet. Schauen wir uns das Beispiel auf der rechten Seite an. Gesucht ist der kürzeste Pfad zwischen A und F.
Die Lösungsidee besteht darin, von A ausgehend den Graphen so zu traversieren ("durchschreiten"), dass als nächstes immer der Knoten besucht wird, der von A die bisher kürzeste Entfernung hat. Wir legen uns dazu eine Tabelle an, in der wir zu jedem Knoten die länge des bisher kürzesten bekannten Pfades nach A notieren: Bei A tragen wir zu Beginn gleich 0 ein, bei allen anderen Knoten den Wert ∞ (unendlich), da wir noch nicht wissen, wie lange der jeweils kürzeste Pfad zu A ist.