Es wird das Verfahren von Dijkstra zur Bestimmung
des kürzesten Weges in einem Graphen eingesetzt. Der Graph kann mit dem graphischen
Editor aufgebaut oder über eine Entfernungsmatrix definiert werden.
Symbole:
i,j,h |
Knotenindizes |
N-i |
Knoten i |
c(i,j) |
Bewertung (Entfernung) des Pfeiles von i nach
j |
MK |
Menge der markierten Knoten |
Entfernung(i) |
Entfernung vom Startknoten a bis zum Knoten
i |
Vorgänger(i) |
direkter Vorgänger von Knoten i auf dem kürzesten
Weg von a nach i |
Annahmen:
- bekannter Digraph mit Bewertungen (Entfernungen) für alle Pfeile im Graphen
Ansicht:
Vor der Durchführung der Berechnungen wird der
Startknoten über ein Dialogfenster abgefragt.
Dabei wird die Knotennummer angegeben, die rechts neben jedem Knoten angezeigt wird.
Nach Abschluß der Berechnungen können die kürzesten Wege aus der Vorgängerliste abgelesen werden.
Im Bild ergibt sich: Levanto <- Mailand <- Basel <- Köln.
Literatur:
- Domschke/Drexl (2007)
|