Dijkstra-Algorithmus
Dijkstra-Algorithmus Definition
Der Dijkstra-Algorithmus berechnet in einem gerichteten Graphen den besten Weg vom ersten bis zum letzten Knoten.
Das kann je nach Aufgabenstellung der kürzeste Weg sein (das ist der Grundfall), der schnellste oder der kostengünstigste. Der Algorithmus ist immer derselbe, aber je nach Aufgabe bewertet man die Kanten / Strecken in dem Graphen mit km, Minuten oder €.
Der Dijkstra-Algorithmus ist ein Greedy-Algorithmus.
Alternative Begriffe: Algorithmus von Dijkstra.
Beispiel
Beispiel: Dijkstra-Algorithmus für den kürzesten Weg
Der Graph umfasst die 4 Knoten bzw. Städte Aachen, Berlin, Celle und Dortmund, die im folgenden mit ihren Anfangsbuchstaben abgekürzt werden.
Die Städte sind durch folgende Bahnstrecken oder Autobahnen mit hier fiktiven km -Angaben verbunden:
A – B: 200 km
A - C: 300 km
B - D: 400 km
C - D: 350 km
Was ist der kürzeste Weg von Aachen nach Dortmund?
Das menschliche Auge sieht jetzt gleich, dass man von A über B nach D mit 200 km + 400 km = 600 km fahren kann oder von A über C nach D mit 300 km + 350 km = 650 km. Die erste Strecke ist die kürzeste.
Der Dijkstra-Algorithmus löst das (auch für Hunderte von Städten und Verbindungen) in mehreren Iterationen (Durchgängen) so:
Beginn
Anfangs trägt man in einer Tabelle die km ein, die man braucht, um direkt von A zu den anderen Knoten zu kommen. Wenn man nicht direkt hinkommt (so wie von A nach D), trägt man unendlich ein. Und von A nach A ist die Entfernung natürlich o km.
Unter die km werden die Vorgängerknoten (Städte, bei denen die jeweilige Strecke beginnt), eingetragen.
Zudem erstellt man eine Menge "Markierte Knoten", aus der man in den folgenden Iterationen jeweils auswählt; zu Beginn sind dies die Knoten, die von A aus erreichbar sind, also B und C.
| A | B | C | D | Markierte Knoten | |
|---|---|---|---|---|---|
| km | 0 | 200 | 300 | unendlich | B, C |
| Vorgänger | - | A | A | - |
Iteration 2
Anschließend wird aus der Menge markierter Knoten der Weg von dem Knoten mit der bisher kürzesten Distanz (also B) weiterverfolgt.
Die Nachfolger(städte) werden betrachtet, von B aus ist das nur D.
Die Entfernung von A nach D über diesen Weg ist 200 km (von A nach B) + 400 km (von B nach D) = 600 km. Das ist weniger (besser) als unendlich, deshalb werden die 600 km bei D eingetragen und D kommt zu C in der Menge markierter Knoten (B ist abgehakt).
| A | B | C | D | Markierte Knoten | |
|---|---|---|---|---|---|
| km | 0 | 200 | 300 | 600 | C, D |
| Vorgänger | - | A | A | B |
Iteration 3
Aus der Menge markierter Knoten wird wieder der Weg von dem Knoten mit der bisher kürzesten Distanz (also C) weiterverfolgt.
Die Nachfolger(städte) werden betrachtet, von C aus ist das nur D.
Die Entfernung von A nach D über diesen Weg ist 300 km (von A nach C) + 350 km (von C nach D) = 650 km. Das ist mehr (schlechter) als die aktuell kürzeste Verbindung nach D mit 600 km.
C ist abgehakt, wird deshalb aus der Menge markierter Knoten entfernt.
Enthalten in der Menge markierter Knoten ist nur noch D selbst, die Endstation. Von hier aus geht es nicht mehr weiter.
Der kürzeste Weg ist von A über B nach D. Man kann den Weg aus der Tabelle rückwärts zusammenbauen: D hat als Vorgängerknoten B gespeichert und B hat als Vorgängerknoten A gespeichert.
In dem Beispiel sieht es so aus, als hätte man alle Wege ausprobiert; das ist hier so, weil das Beispiel so klein ist. Der Dijkstra-Algorithmus rechnet nicht einfach alle Wege durch und nimmt den kürzesten, er bricht i. d. R. vorher ab, weil er die Lösung schon gefunden hat.