Home Produktions-Management-Trainer ÜbersichtTaktische PlanungOperative PlanungVerschiedenesEnglish Pages
 

Bestimmung des kürzesten Weges in einem Graphen (Dijkstra-Verfahren)

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)

Copyright ©2013 POM Prof. Tempelmeier GmbH All rights reserved. | Unternehmen | Kontakt | Impressum |