Kürzeste Pfade nach Dijkstra (Algorithmus 4.9)

So geht’s: Beim Öffnen läuft der Testclient mit tinyEWD und Start s = 0, in derselben Lage wie in Abbildung 4.74. Die Zahlen an den Pfeilen sind die Gewichte. Jede Runde beginnt mit pq.delMin(): Der Knoten mit dem kleinsten distTo wird orange, sein Abstand ist damit endgültig (danach grün). Dann relaxiert relax seine ausgehenden Kanten, die gerade geprüfte ist blau gestrichelt. Wird ein Weg kürzer, ändern sich edgeTo[] und distTo[] rechts, und der Knoten kommt in die Warteschlange oder rückt darin nach oben. Rot umrandet sind die Knoten in der Warteschlange, ihre rote Kante ist die bisher beste letzte Kante. Schwarz ist der Baum der kürzesten Pfade. Am Ende zeigt die Ausgabe für jeden Knoten seinen Pfad, er leuchtet dabei orange auf. „ab s“ startet von einem anderen Knoten aus, „Zufallsgraph“ erzeugt einen neuen Digraphen, „↺ Neu starten“ springt zurück zu tinyEWD.

Erklärung

Kürzeste Pfade nach Dijkstra (Algorithmus 4.9), Klasse DijkstraSP. Abschnitt 4.4. Jetzt ein gerichteter, kantengewichteter Graph. Gesucht: die kürzesten Pfade von einem Startknoten s zu allen anderen, gemessen an der Summe der Kantengewichte (nicht an der Kantenzahl wie bei der Breitensuche [31]).

Voraussetzung: Alle Gewichte sind nicht negativ.

Grundoperation: Relaxierung

• distTo[w]: Länge des bisher kürzesten bekannten Pfads von s nach w.
• edgeTo[w]: letzte Kante auf diesem Pfad.
• Für eine Kante v→w prüft man: Ist der Weg über v kürzer als das bisher Bekannte, also distTo[v] + Gewicht < distTo[w]? Wenn ja, distTo[w] und edgeTo[w] aktualisieren. Das ist „relaxieren“: Die Schätzung wird lockerer, sprich besser.

Der Code:

• Anfangs alle distTo unendlich, nur distTo[s] = 0.
• s in die indizierte Vorrangwarteschlange [37].
• Solange nicht leer: Knoten mit kleinstem distTo herausnehmen und alle seine ausgehenden Kanten relaxieren.
• Wird distTo[w] verbessert: w in der Schlange einfügen oder Schlüssel senken.

Fast identisch mit Prim [37]. Der einzige echte Unterschied steckt in einer Zeile:

• Prim: Schlüssel ist das Gewicht der einzelnen Kante zum Baum (e.weight()).
• Dijkstra: Schlüssel ist die Gesamtlänge des Pfads von s (distTo[v] + e.weight()).
• Prim baut den leichtesten Baum, Dijkstra den Baum der kürzesten Wege. Das sind im Allgemeinen verschiedene Bäume.

Abbildung 4.74 (tinyEWD.txt, Start 0), Reihenfolge des Herausnehmens:

Die Knoten kommen in aufsteigender Reihenfolge ihres Abstands zu s heraus. Beispielpfad zu 6: 0→2→7→3→6, Länge 0,26 + 0,34 + 0,39 + 0,52 = 1,51. Für jede Baumkante v→w gilt distTo[w] = distTo[v] + Gewicht(v→w).

Warum korrekt? Wird v aus der Schlange genommen, hat es den kleinsten distTo aller noch offenen Knoten. Jeder andere Weg zu v müsste über einen dieser offenen Knoten laufen, der schon mindestens so weit weg ist, und weil Gewichte nicht negativ sind, kann es danach nicht kürzer werden. Also ist distTo[v] ab diesem Moment endgültig.

Satz R: Dijkstra berechnet den Kürzeste-Pfade-Baum mit Zusatzspeicher proportional zu V und Zeit proportional zu E log V im schlimmsten Fall.

Grenzen und was folgt:

• Negative Gewichte → Dijkstra kann falsch liegen, weil ein „endgültiger“ Knoten später doch noch billiger erreicht werden könnte. Dafür Bellman-Ford (Algorithmus 4.11).
• Azyklischer Digraph → schneller und einfacher über topologische Ordnung [34], linear und auch mit negativen Gewichten (Algorithmus 4.10).
• Typische Anwendung: Routenplanung, Netzwerk-Routing.

Stand Kapitel 4:

• Algorithmus 4.1: Tiefensuche für Pfade [30]
• Algorithmus 4.2: Breitensuche für kürzeste Pfade [31]
• Algorithmus 4.3: Zusammenhangskomponenten [32]
• Algorithmus 4.4: Erreichbarkeit in Digraphen [33]
• Algorithmus 4.5: Topologisches Sortieren [34]
• Algorithmus 4.6: Starke Komponenten nach Kosaraju [35], [36]
• Algorithmus 4.7: Minimaler Spannbaum nach Prim [37]
• Algorithmus 4.8: Minimaler Spannbaum nach Kruskal [38]
• Algorithmus 4.9: Kürzeste Pfade nach Dijkstra [39]