Erklärung:
Es soll der kürzesten Weg - so wie vorgeschlagen - zwischen zwei Knoten bestimmt werden.
Bei großer Knotenzahl und langem Weg, entsteht ein riesiger Baum um den Startknoten.
Leider kann man am Anfang nicht auf Wege verzichten, weil man ja nicht die Richtung kennt.
Anders, wenn man die Geografischen Koordinaten der Knoten kennt
Man kann alle fortführende Wege von Knoten ausschließen, von denen die Summe aus Länge zum Startknoten und Luftlinienabstand zum Endknoten eine bekannte Weglänge übersteigt. Ferner müssen die hinführenden Wege vom Startknoten zu diesen Knoten kürzeste Wege sein.
Ob diese Wege die kürzesten sind, zeigt das gleiche Kriterium wie das vom Zielknoten.
Ferner braucht man einen bekannten Weg zum Zielknoten für die Vergleichslänge.
Eine sichere Methode, um einen Weg vom Start zum Ziel zu finden, ist ein Back-Track-Stapel.
Dem interessiert aber nicht, wie lang der Weg ist.
Dieser Back-Track-Stapel funktioniert wie der Weg der Maus durch ein Labyrinth. Wenn ein Weg als falsch erkannt wird, geht er einen Schritt zurück oder der Knoten wird gar nicht zugefügt, und es wird der nächsten Ausgang verwendet.
Voraussetzung:
Alle Ausgänge von irgend einem Knoten sind nummeriert, und es muss der jeweilige maximale Index (Ausgangsnummer) bekannt sein.
Dieser Stapel findet immer einen Weg, und wenn kein Weg existiert, erkennt er dies auch.
Das Stapelelement genügt, wenn es eine Knotenkennung, und die nächste Ausgangsnummer enthält.
Meist dient der Back-Track-Stapel dazu, um Sackgassen und Zyklen zu vermeiden. Im Transport-Problem wird er benutzt um einen Zyklus zu finden.
In diesem Beispiel werden die Ausgänge sortiert nach dem Abstand der Geografischen Koordinaten der Kantenenden zum Endknoten.
Weil der gleiche Knoten von verschieden Knoten ausgehend erreicht werden kann, erhält man das gleiche Endresultat, wenn man schon besuchte Knoten nicht weiter verfolgt.