Kürzeste-Wege-Problem

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

Das Kürzeste-Wege-Problem besteht allgemein darin, in einem gegebenen Netzwerk (bestehend aus Knoten und gerichteten, mit Entfernungen bzw. Kosten bewerteten Kanten) den kürzesten bzw. kostengünstigsten Weg von einem Startknoten zu einem Zielknoten zu bestimmen. Dieses Problem tritt z.B. in der Logistik auf, wenn ein Lieferfahrzeug eine Warensendung von einem Startort A zu einem Zielort B transportieren soll. Wenn der Ort B nicht ein direkter Nachbarort des Ortes A ist, dann benötigt man ein systematisches Verfahren zur Bestimmung der Fahrstrecke. Auch beim Einssatz eines Navigationssystems in einem PKW treten regelmäßig Kürzeste-Weg-Probleme auf.

Unabhängig von der räumlichen Sichtweise des Problems lassen sich auch andere Fragestellungen als Kürzeste-Wege-Probleme modellieren. So kann man z.B. das Problem der dynamischen Einprodukt-Losgrößenplanung ohne Kapazitätsbeschränkungen als Kürzeste-Wege-Problem modellieren. In diesem Fall repräsentieren die Knoten die einzelnen Perioden und die gerichteten Kanten beschreiben die Lagerung der Produktmengen. Die "Entfernungen" sind dann die gesamten Rüst- und Lagerkosten. Ein Beispiel hierzu ist in Günther/Tempelmeier (2020a) beschrieben.

In diesem Modul wird das Verfahren von Dijkstra zur Bestimmung des kürzesten Weges in einem Graphen eingesetzt. Die Struktur des Graphen wird mit dem graphischen Editor aufgebaut.

Symbole:

i, j, h	Indizes der Knoten
N-i	Knoten i
c(i,j)	Bewertung (Entfernung, Kosten, etc.) 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 gerichteter Graph 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. Man startet mit dem Zielort (Levanto) und sucht dessen Vorgänger (Mailand) auf dem kürzesten Weg von Köln zum Zielort. Dann sucht man den Vorgänger (Basel) des Vorgängers (Mailand). Im Bild ergibt sich: Levanto <- Mailand <- Basel <- Köln.

Literatur:

- Domschke/Drexl (2005)