Kürzesten Weg finden



schrittweise Iteration
Iteration auf einmal

mit EndKnotenIndex

Es wird der kürzeste Weg zwischen zwei Knoten im Netzwerk gesucht,
mit einer Variante der Methode von Dijkstra.
Dazu werden alle Wege zu Nachbarknoten betrachtet. Notiert werden nur die
kürzesten Wege zwischen zwei Knoten. Wenn man auf den Endknoten
trifft, und alle neuen Wege länger sind, ist die Suche beendet.
0 Anzahl Iterationen. X km Länge zwischen Knoten XXXXXX und XXXXX.
Knoten  Kanten  kürzeste Wege
  


Erklärung:
Als Erstes wird ein sortierter Vektor von allen Kanten gebildet, in dem beide Richtungen der Kante eingefügt werden. Kanten, die zum Anfangsknoten führen und solche, die vom Endknoten weggehen, werden nicht notiert. Es wird nicht der kürzeste Weg gesucht, sondern ausgehend vom Start-Knoten werden alle Wege, pro Iteation um eine Kante verlängert.
Im Iterationsschritt werden alle neuen Pfade notiert. Hat dabei ein Weg schon einen vorhandenen letzten Knoten, wird er nicht dazugenommen, wenn er nicht kürzer als der schon vorhandene ist.
Andernfalls wird der alte mit dem neuen ausgetauscht. Die Position des neuen Pfades in der Pfad-Liste bleibt die Position vom alten Pfad. Die davon abhängigen Pfade müssen korrigiert werden. Es enstehen maximal n-1 Pfade (zu allen Knoten ohne zum Startknoten).
Ende der Iterationen:

Die Endknoten einer Iteraton hängen alle von den Endknoten der voran gegangen Iteration ab, außer wenn ein Pfad ausgetauscht wurde. Das kann aber nur in einer Erweiterung mit gleicher oder größerer Iterationszahl passieren.
Der optimale Pfad unterscheidet sich vom aktuellen Pfad, höchstens um die Differenz zum kürzesten Pfad der aktuellen Iteration. So ist der optimale Pfad gefunden, wenn alle anderen (neuen) Pfade der aktuellen Iteration nicht kürzer sind.
Weil sich die Position der End-Knoten in der Pfadliste nicht ändert, kann man einen Index auf die Endknoten erstellen. Das verkürzt die Zeit zum nachschauen, ob ein Endknoten schon vorhanden ist.

   
Knoten neu/ändern
Kurzbez .:
Name:
 Mittelknoten  Startknoten  Endknoten
   
Kante neu/ändern
Kurzbez .K1:
Kurzbez .K2:
Länge: