Der Algorithmus von Dijkstra
Wie früher stellt sich die Frage:
Wie können wir dw(a, b) und einen zugehörigen Weg von a nach b berechnen?
Sind die Kantengewichte natürliche Zahlen, so können wir das neue Problem prinzipiell auf das alte Problem zurückführen: Ist ab eine Kante mit Gewicht w(ab) = m ∈ ℕ, so entfernen wir die Kante ab und führen neue Ecken e1, …, em − 1 zusammen mit neuen ungewichteten Kanten ae1, e1e2, …, em − 1b ein. Für jede Kante durchgeführt liefert dies einen ungewichteten Graphen G′ = (E′, K′). Für Ecken a, b in E können wir nun den ungewichteten Abstand d(a, b) zwischen a und b in G′ durch Breitensuche berechnen. Nach Konstruktion ist dieser Abstand gleich dem gewichteten Abstand dw(a, b) von a und b in G. Für rationale Kantengewichte können wir diese Übersetzung durch Multiplikation mit dem Hauptnenner ebenfalls durchführen. Das ist aber alles nicht besonders schön und vor allem auch nicht effizient. Besser ist es, nach einem neuen Algorithmus zu suchen, der auf die verallgemeinerte Situation zugeschnitten ist. Dies leistet der Algorithmus von Dijkstra (1959) [ gesprochen: Deikstra ].
Wie die Breiten- und Tiefensuche konstruiert der Algorithmus von Dijkstra von einer Startecke ausgehend einen aufspannenden Baum eines zusammenhängenden Graphen durch schrittweises Anfügen neuer Grenzkanten. Zusätzlich berechnet er die gewichteten Abstände von der Startecke zu den besuchten Ecken, und diese Abstände werden zur Auswahl der nächsten Grenzkante eingesetzt. In einem Satz lautet der Algorithmus:
Minimiere den gewichteten Abstand der nächsten besuchten Ecke zur Startecke.
Genauer gilt:
Algorithmus von Dijkstra
Sei G = (E, K, w) ein gewichteter zusammenhängender Graph der Ordnung n, und sei e0 ∈ E (Startecke). Wir definieren rekursiv Ecken e1, …, en − 1, Kanten k1, …, kn − 1 und Abstandswerte d(e0), …, d(en − 1) wie folgt.
Zunächst sei d(e0) = 0. Sei nun m ≥ 0, und seien
(+) e0, …, em, k1, …, km, d(e0), …, d(em)
berechnet. Ist m = n − 1, so stoppen wir mit Ausgabe von (+). Andernfalls betrachten wir alle Grenzkanten des konstruierten Baumes, d. h. alle Kanten, die eine besuchte Ecke e0, …, em mit einer unbesuchten Ecke verbinden. Für jede derartige Kante k = eie berechnen wir die Summe
g(k) = d(ei) + w(eie).
Wir wählen nun eine Kante k* = ei*e* mit minimalem g-Wert und setzen
em + 1 = e*, km + 1 = k*, d(em + 1) = d(ei*) + w(k*).
Die Konstruktion liefert einen aufspannenden Baum von G, dessen Ecken mit Abstandswerten versehen sind. Dieser Suchbaum wird ausgehend von der Startecke durch schrittweises Anfügen von optimalen Grenzkanten konstruiert. Die Optimalität ist durch die Gewichtsfunktion und die berechneten Abstandswerte erklärt. Nach Konstruktion gilt
d(e0) ≤ d(e1) ≤ … ≤ d(en − 1).
Weiter zeigen wir:
Satz (Korrektheit des Algorithmus von Dijkstra)
Mit den obigen Bezeichnungen gilt für alle 0 ≤ m < n:
(a) | d(em) = dw(e0, em). |
(b) | Der eindeutige Weg von e0 nach em im Suchbaum ist ein Weg von e0 nach em mit minimalem Gewicht. |
Beweis
Wir zeigen die Aussage (a) durch Induktion nach m. Hieraus folgt (b), da der Weg von e0 zu em im Suchbaum nach Konstruktion das Gewicht d(em) besitzt. Aufgrund der Existenz dieses Weges genügt es, dw(e0, em) ≥ d(em) zu zeigen.
Induktionsanfang m = 0:
Es gilt d(e0) = 0 = dw(e0, e0).
Induktionsschritt von m nach m + 1:
Sei a0, a1, …, ar − 1, ar ein Weg von e0 nach em + 1 mit minimalem Gewicht. Weiter sei j maximal in der Menge { 0, …, r − 1 } mit der Eigenschaft
aj ∈ { e1, …, em }.
Dann gibt es genau ein i ∈ { 1, …, m } mit aj = ei. Unter Verwendung der Optimalität von Teilstücken und der Induktionsvoraussetzung erhalten wir:
| dw(e0, em + 1) | = ℓw(a0, …, ar) |
| = ℓw(a0, …, aj) + w(aj aj + 1) + ℓw(aj + 1, …, ar) | |
| ≥ ℓw(a0, …, aj) + w(aj aj + 1) | |
| = dw(e0, aj) + w(aj aj + 1) | |
| = dw(e0, ei) + w(ei aj + 1) | |
| = d(ei) + w(ei aj + 1) | |
| ≥ d(em + 1). |
Bei der letzten Ungleichung verwenden wir, dass bei der Definition von em + 1 über einen minimalen g-Wert die Kante k = ei aj + 1 zu den betrachteten Kanten gehört (da aj + 1 ∉ { e1, …, em }).
Ist G nicht zusammenhängend, so berechnet der Algorithmus von Dijkstra die gewichteten Abstände in der Zusammenhangskomponente der Startecke. Sind wir an allen Abständen dw(a, b) für a, b ∈ E interessiert, so müssen wir wie bei der Breitensuche den Algorithmus für alle Startecken durchführen. Nach n Durchläufen ist die Funktion dw vollständig bestimmt.
Damit haben wir einen effizienten Algorithmus zur Berechnung von gewichteten Abständen und zugehörigen Wegen gefunden. Die Laufzeit ist für jede Startecke quadratisch in |E|.
In den folgenden Beispielen nehmen wir immer an, dass E von der kanonischen Form { 1, …, n } ist. Um einen deterministischen Ablauf sicherzustellen, folgen wir dem Prinzip der kleinsten Wahl.
Beispiel
Sei G = (E, K, w) mit E = { 1, 2, 3, 4 } und
K = { 12, 13, 24, 34 }, w(12) = 1, w(13) = 3, w(24) = 6, w(34) = 1.
Mit der Startecke 1 ist e0 = 1 und d(1) = 0. Nun berechnen wir den Suchbaum und die gewichteten Abstände zur Startecke:
(1) | Die unbesuchten Nachbarn der besuchten Ecke 1 sind 2 und 3. Die Kante 12 ist g-minimal, sodass e1 = 2, k1 = 12, d(2) = d(1) + w(12) = 0 + 1 = 1. |
(2) | Die unbesuchten Nachbarn der besuchten Ecken 1, 2 sind 3 und 4. Die Kante 13 ist g-minimal, da d(1) + 3 = 3 < 7 = d(2) + 6. Also ist e2 = 3, k2 = 13, d(3) = d(1) + w(13) = 0 + 3 = 3. |
(3) | Einziger unbesuchter Nachbar der besuchten Ecken 1, 2, 3 ist 4. Die Kante 34 ist g-minimal, da d(3) + 1 = 4 < 7 = d(2) + 6. Es gilt e3 = 4, k3 = 34, d(4) = d(3) + w(34) = 3 + 1 = 4. |
Es ist nützlich (vor allem für größere Graphen), den Verlauf des Algorithmus tabellarisch zu protokollieren. Eine Möglichkeit hierzu zeigt folgende Tabelle:
Schritt | 0 | 1 | 2 | 3 |
Ecke 1 | 0 | − | − | − |
Ecke 2 | 0 + 1 = 1 | − | − | |
Ecke 3 | 0 + 3 = 3 | 3 | − | |
Ecke 4 | 1 + 6 = 7 | 3 + 1 = 4 | ||
Abstand d(e) | 0 | 1 | 3 | 4 |
Besuchte Ecke | 1 | 2 | 3 | 4 |
Verwendete Kante | 12 | 13 | 34 |
Zur Erstellung der Tabelle
(1) | Die Spalten der Tabelle werden nacheinander gefüllt. Die Einträge in den Ecken-Zeilen der Schritte 1, …, n − 1 sind gewisse Werte der g-Funktion. Wir nennen sie auch Approximationen. |
(2) | Ausnahme von (1): Sobald eine Ecke e besucht wird, füllen wir die Zeile von e bis zum Ende mit Strichen, die für „fertig bearbeitet“ stehen. Bevor also zum Beispiel die Spalte des Schritts 1 mit „1, 3“ gefüllt wird, wird die Zeile der Ecke 1 mit Strichen gefüllt. |
(3) | Zur Berechnung der Approximationen der Spalte m + 1 werden die unbesuchten Nachbarn von em ermittelt. Für jeden solchen Nachbarn a berechnen wir den g-Wert d(em) + w(ema). Ist ein solcher Wert ein Neueintrag in der Zeile der Ecke a oder besser als der bisher gefundene, so tragen wir ihn in der Zeile a und Spalte m + 1 ein. Andernfalls übernehmen wir den alten Wert. Gefundene Approximationen werden also solange übernommen oder verbessert, bis die Ecke besucht wird. |
(4) | Der Wert d(em), die Ecke em und die Kante km sind durch das erste Minimum der Approximationen der Spalte m definiert: d(em) ist dieses Minimum, em die Zeile dieses Minimums und km ist die Kante, die verwendet wurde, als das Minimum als g-Wert in der Spalte i gefunden wurde. Eine Ecke von km ist em, die andere ist ei − 1. |
Mit Hilfe der Tabelle lässt sich der Algorithmus durchführen, ohne den Graphen zu zeichnen. Sie eignet sich für eine Implementierung des Algorithmus. Auch die Approximationswerte sind von Interesse: Der Eintrag einer Ecke e in der Spalte des Schritts m gibt das minimale Gewicht eines Weges von der Startecke nach e an, der höchstens m + 1 Ecken besucht. Ein leerer Eintrag ist dabei als „Abstand ∞“ oder „nicht erreichbar“ zu lesen.
Zur weiteren Illustration betrachten wir noch ein etwas komplizierteres Beispiel.
Beispiel
Sei G = (E, K, w) mit E = { 1, 2, 3, 4, 5, 6, 7 } und
K = { 12, 13, 14, 23, 25, 34, 35, 36, 37, 47, 56, 67 },
w(12) = 3, w(13) = 10, w(14) = 9, w(23) = 6, w(25) = 2, w(34) = 3,
w(35) = 2, w(36) = 3, w(37) = 5, w(47) = 1, w(56) = 1, w(67) = 1.
Für die Startecke 1 erhalten wir:
Schritt | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
Ecke 1 | 0 | − | − | − | − | − | − |
Ecke 2 | 0+3 = 3 | − | − | − | − | − | |
Ecke 3 | 0+10 = 10 | 3+6 = 9 | 5+2 = 7 | 7 | − | − | |
Ecke 4 | 0+9 = 9 | 9 | 9 | 9 | 9 | 7+1 = 8 | |
Ecke 5 | 3+2 = 5 | − | − | − | − | ||
Ecke 6 | 5+1 = 6 | − | − | − | |||
Ecke 7 | 6+1 = 7 | 7 | − | ||||
Abstand d(e) | 0 | 3 | 5 | 6 | 7 | 7 | 8 |
Besuchte Ecke | 1 | 2 | 5 | 6 | 3 | 7 | 4 |
Verw. Kante | 12 | 25 | 56 | 35 | 67 | 47 |
Das folgende Diagramm zeigt den konstruierten aufspannenden Baum, die Besuchsfolge der Ecken und die berechneten Abstände.