Um den Kürzesten Weg von unten folgendem Beispiel zu finden, muss Dijkstra's Algorithmus angewendet werden.
Dazu sieht man sich jeden Knotenpunkt einzeln an, und untersucht seine Nachbarknoten. Man trägt in eine Tabelle ein, wie lang der Weg vom Ausgangsknoten zum aktuellen Knoten ist und gibt dazu den neuen "Parent-Knoten" an. Um sicher zu gehen, dass man wirklich den kürzesten Weg ausgewählt hat, muss man wirklich jeden Knoten einzeln abarbeiten.
Folgende Tabelle ist bei mir dadurch herausgekommen:
Dazu sieht man sich jeden Knotenpunkt einzeln an, und untersucht seine Nachbarknoten. Man trägt in eine Tabelle ein, wie lang der Weg vom Ausgangsknoten zum aktuellen Knoten ist und gibt dazu den neuen "Parent-Knoten" an. Um sicher zu gehen, dass man wirklich den kürzesten Weg ausgewählt hat, muss man wirklich jeden Knoten einzeln abarbeiten.
Folgende Tabelle ist bei mir dadurch herausgekommen:
Die roten Linien im Diagramm zeigen den jeweils kürzesten Weg zu jedem Knoten:
Hier noch der kürzeste Weg von Knoten A zu Knoten K in der Tabelle angeführt:
Die Angabe zu diesem Beispiel findet ihr unter www.ksn3.blogspot.co.at
