Grundlage für die Berechnung eines Kürzesten Weges zwischen zwei Punkten ist das so genannten Knoten-Kanten-Modell.
Knoten ... ist ein Punkt, bei dem ein oder mehrere Kanten enden (anfangen)
Kante ... lineare Verbindung zwischen zwei Knoten. Eine Kante
kann ein Bogen, eine Linienzug oder eine Linie sein
Typische Beispiele für ein Knoten-Kanten-Modell ist das Straßennetz oder ein Wasser-Leitungsnetz. Bei einem Straßennetz sind die Kreuzungen und Enden von Sackgassen die Knoten, die Straßenstücke dazwischen die Kanten.
Ein Knoten-Kanten-Modell erlaubt das Routing, d.h. das Verkehrs-Berechnungen oder Wasserversorgungsthematiken. Ein typisches Beispiel im Verkehrswesen ist die Routenplanung von einem Ort X zum Ort Y, wie es heute von den Auto-Navi-Geräten jedermann bekannt ist.
Für die Berechnung des "Kürzesten Weges" wurden verschiedene Algorithmen entwickelt. Verbreitet ist der Algorithmus von Edsger W. Dijkstra.
Ausgangspunkt ist ein Knoten-Kantenmodell, wobei die Kanten positive Werte (Gewichte) haben. Das kann z.B. die Entfernung zwischen zwei Orten sein oder Durchfließgeschwindigkeit. Ausgehend vom Startknoten wird jener Kante gefolgt, die das kleinste Gewicht haben. Dies wird für jeden Knoten ausgeführt, wobei dann immer die Summe der Teilabschnitte das Kriterium der Kantenauswahl darstellt. Der Algorithmus wird so lange fortgesetzt, bis der Weg mit der Summe des kleinsten Gewichtes zum Endpunkt erreicht ist. Im Detail werden folgende Schritte ausgeführt:
(1) Es wird eine Gewichtungs/Entfernungs-Matrix erzeugt. Im Normalfall ist die Diagonale mit 0 besetzt und die Werte symmetrisch dazu besetzt.
(2) Zu jedem Knoten werden drei zusätzliche Informationfelder bereitgestellt. - Vorgänger: Angabe des vorherigen Knoten - Gewicht(Entfernung)-Summe: Summe der Gewichte/Entfernungen vom Anfangspunkt - Zustand: Endgültig oder Provisorisch
Bei allen Knoten wird die Gewichtssumme auf "Unendlich" und der Zustand auf "Provisorisch" gesetzt.
Beim Startknoten wird die Gewichtssumme auf "0" und der Zustand auf "Endgültig" gesetzt. Er ist der erste Vergleichsknoten
(3) Es werden alle Knoten gesucht, die mit dem Vergleichsknoten verbunden ist und stellt ihre Werte ein.
(4) Es wird jener Knoten ausgewählt, der die kleinste Gewichtssumme besitzt. Dies ist der neue Vergleichsknoten.
(5) Die Schritte 3 bis 5 werden so lange wiederholt, bis der Vergleichsknoten mit dem Endknoten ident ist.
(6) Über das Informationsfeld "Vorgänger" kann nun die gesamte Liste des kürzesten Weges ermittelt werden.
Der Dijkstra-Algorithmus funktioniert nur für Knoten-Kanten-Modelle, wo die Kanten positive Werte (Gewichte) haben. Bei negativen Werten empfiehlt sich die Anwendung des Bellman-Ford-Algorithmus.
Die Ermittlung des kürzesten Weges ist in geoLion möglich. Der Ablauf ist folgender:
(1) Zeichnen des Knoten-Kanten-Modells
Symbole sind die Knoten, Linienzüge die Kanten.
Wichtig ist, dass jeder Ort ein Attribut mit einer Spalte "NAME" hat, der z.B. den Ortsnamen enthält. So ist es dann möglich den kürzesten Weg zwischen Ort X und Y abzufragen. Hat auch die Straße ein Attribut mit dem Spalte "NAME" und darin ist der Straßenname eingetragen, so gibt das Abfrageergebnis diese zusätzliche Informationen bekannt.
(2) Berechung des Knoten-Kanten-Modells
Damit die Abfragen rasch Ergebnisse liefern, wird in
einem Vorbereitungsschritt das Knoten-Kanten-Modell aus
der Graphik generiert. D.h. sobald es zu Veränderungen
in der Graphik kommt, ist das Knoten-Kanten-Modell neu
zu erstellen. Der Befehl dazu lautet:
Der Keyin(Eingabe)-Befehl lautet:
ROUTE CREATE Knoten-Ebene Kanten-Ebene
Im Hintergrund legt das Programm drei Dateien ab, eine mit den Knoten-Informationen, eine mit den Kanten-Informationen und eine die Gewichtungsmatrix.
(3) Abfragen nach dem kürzesten Weg
Der Keyin(Eingabe)-Befehl lautet:
ROUTE SEARCH Anfangsknoten Endknoten Knoten-Ebene,Kanten-Ebene
Der Anfangs- und Endknoten wird mit Eintrag aus der "NAME"-Spalte angegeben. D.h. mit der Angabe des Ortsnamen.
Wenn es einen kürzesten Weg gibt, dann wird das Ergebnis in der Graphik farblich hervorgehoben und die gefundenen Kanten selektiert.