R2 Wegeprobleme
Dijkstra-Algorithmus
Dijkstra-Algorithmus anhand eines Beispiels
In diesem und den nächsten Abschnitten wird auf den Dijkstra-Algorithmus zur Lösung von Kürzeste-Wege-Problemen eingegangen. Er funktioniert sowohl in gerichteten als auch ungerichteten Netzwerken. Negative Kantengewichte sind dabei nicht zulässig.
Zunächst wird der Algorithmus anhand eines Beispiels vorgestellt und anschließend in einer algorithmischen Beschreibung zusammengefasst.
Beispiel Dijkstra-Algorithmus
Initialisierung
Es wird zwischen endgültig und vorläufig markierten Knoten unterschieden. Zu Beginn der Rechnung ist nur A endgültig markiert.
Eine endgültige Markierung kann bei einer Papier-und-Bleistift-Rechnung durch Ausmalen des Knotensymbols gekennzeichnet werden.
Ferner erhalten alle Knoten eine zweiteilige Markierung. Der erste Teil weist auf den Vorgängerknoten auf dem kürzesten bekannten Weg hin, der zweite Teil gibt die Länge des kürzesten bekannten Weges zu dem jeweiligen Knoten an. Wenn nur die Länge des kürzestes Weges interessiert, nicht aber die Knoten über die er führt, kann auf den ersten Teil der Markierung verzichtet werden.
Der Startknoten A erhält die Markierung -;0 .
Alle Knoten die über eine Kante mit dem Knoten A verbunden sind, werden vorläufig mit A als Vorgänger und dem Kantengewicht cAj markiert. Im Beispiel sind das B und C.
Alle anderen Knoten werden mit -;∞ markiert.
Damit sind die Vorbereitungen abgeschlossen und die 1. Iteration kann durchgeführt werden.
Iteration 1
Schritt 1: Wahl des Arbeitsknotens
Es werden nur die vorläufig markierten Knoten betrachtet. Unter diesen Knoten wird derjenige mit der kleinsten Markierung gesucht, im Beispiel Knoten C.
Dieser Knoten wird endgültig markiert.
Schritt 2: Aktualisieren der vorläufigen Markierungen
Nun werden alle vom Knoten C ausgehenden Kanten zu vorläufig markierten Knoten betrachtet, also (C;B) und (C;E).
Ist die Summe aus Markierung von C und Kantengewicht cCB bzw. cCE kleiner als die vorläufige Markierung des betrachteten Knotens B bzw. E? Wenn ja, wird die Markierung angepasst.
Für Kante (C;B): 2+2=4<5 --> Markierung von B durch C;4 ersetzen.
Für Kante (C;E) :2+ 5=7<∞ --> Markierung von E durch C;7 ersetzen.
Damit ist die erste Iteration abgeschlossen und es geht weiter mit Schritt 1.
Iteration 2
Schritt 1:
Der nur vorläufig markierte Knoten mit der kleinsten Markierung ist B mit 4. Er wird endgültig markiert und als Arbeitsknoten gewählt..
Schritt 2:
Von Knoten B führen Kanten zu D und E. Wir aktualisieren die Bewertungen.
Für Kante (B;D): 4+5=9<∞ --> Markierung von D durch B;9 ersetzen.
Für Kante (B;E): 4+7=11 > 7 -->Markierung von E bleibt unverändert.
Iteration 3
Schritt 1:
Kleinster vorläufig markierter Knoten ist E mit 7. Endgültig markieren und als Arbeitsknoten verwenden!
Schritt 2:
Für Kante (E;D): 7+4=11 > 10 --> Markierung von D bleibt unverändert
Für Kante (E;Z): : 7+4=11 <∞ --> Markierung von Z auf E;11 setzen.
Iteration 4:
Schritt 1:
Kleinster vorläufig markierte Knoten ist D mit 9. Endgültig markieren und als Arbeitsknoten verwenden!
Schritt 2:
Für Kante (D;Z) :9+1=10 <11, Markierung von Z auf D;10 setzen.
Iteration 5:
Schritt 1:
Der kleinste vorläufig markierte Knoten ist Z, er wird endgültig markiert und das Verfahren kann beendet werden.
Der kürzeste Weg von A nach Z hat eine Länge von 10.
Der Weg lässt sich über die Markierungen rückwärts ablesen: Z verweist auf D, D auf B, B auf C und C auf A.
Also ist der kürzeste Weg A-C-B-D-Z
Kürzester Weg von A nach Z vs. kürzester Weg von A zu allen Knoten
Grundsätzlich kann das Verfahren beendet werden, wenn der Knoten Z endgültig markiert ist, oder es keine vorläufig markierten Knoten mehr gibt. Im obigen Beispiel ist beides zeitgleich der Fall, sodass es keinen Unterschied macht.
Wenn nur der kürzeste Weg von A nach Z gesucht ist, kann die Rechnung beendet werden, wenn Z endgültig markiert ist und so Arbeit gespart werden.
Wird das Verfahren fortgesetzt, bis alle Knoten markiert sind, ist das Ergebnis nicht nur der kürzeste Weg von A nach Z, sondern der zu allen erreichbaren Knoten.
Bemerkungen zu besonderen Fällen:
- Haben mehrere Knoten die gleiche kleinste Markierung, kann ein beliebiger ausgewählt werden.
- Ist die Summe aus Markierung von i und Kantengewicht cij gleich der vorläufigen Markierung von j, kann die Markierung ersetzt werden oder auch nicht.
- Werden aus Versehen von dem in Schritt 1 ausgewählten Knoten auch die Kanten zu bereits endgültig markierten Knoten betrachtet, ist das Ergebnis immer, dass die Markierung nicht ersetzt wird. Anderenfalls liegt ein Rechenfehler vor oder der Graph hat Kreise mit negativer Länge und der Dijkstra-Algorithmus hätte nicht angewendet werden dürfen.
- Ist die kleinste vorläufige Markierung unendlich, existiert kein Weg von A zu dem vorläufig markierten Knoten und das Verfahren bricht ohne Ergebnis ab.
Eine Feststellung zu kürzesten Wegen allgemein
Wenn ein kürzester Weg w zwischen zwei Knoten A und Z über den Knoten K führt, dann ist der Teilweg von A nach K w‘ auch ein kürzester Weg zwischen A und K.
Gäbe es einen kürzeren Weg v‘ von A nach K, dann könnte man durch Nutzung dieses auch den Weg von A nach Z verkürzen und w wäre kein kürzester Weg.
