Kürzeste Pfade in azyklischen Digraphen (Algorithmus 4.10)

So geht’s: Beim Öffnen läuft der Testclient mit tinyEWDAG und Start s = 5, in derselben Lage wie in Abbildung 4.77. Die Zahlen an den Pfeilen sind die Gewichte. Zuerst berechnet Topological die Ordnung 5 1 3 6 4 7 0 2 (rechts unter der Tabelle). Dann kommt jeder Knoten genau einmal dran, in dieser Reihenfolge: Der laufende ist orange, die erledigten sind grün. relax prüft seine ausgehenden Kanten, die gerade geprüfte ist blau gestrichelt. Wird ein Weg kürzer, ändern sich edgeTo[] und distTo[] rechts. Rot sind Kanten, die nur vorläufig im Baum stehen, weil ihr Zielknoten noch nicht dran war. Schwarz ist der fertige Baum der kürzesten Pfade, grau gestrichelt sind Kanten, die nicht auswählbar sind (sie bringen nichts oder wurden verdrängt, wie 6→0 und 6→2). Am Ende zeigt die Ausgabe für jeden Knoten seinen Pfad, er leuchtet dabei orange auf. „ab s“ startet von einem anderen Knoten aus, „Zufalls-DAG“ erzeugt einen neuen azyklischen Digraphen, auch mit negativen Gewichten, „↺ Neu starten“ springt zurück zu tinyEWDAG.

Erklärung

Kürzeste Pfade in kantengewichteten azyklischen Digraphen (Algorithmus 4.10), Klasse AcyclicSP. Gleiche Aufgabe wie Dijkstra [39], aber für den Sonderfall ohne Zyklen (DAG). Dann geht es schneller, einfacher und sogar mit negativen Gewichten.

Idee: Die Knoten in topologischer Reihenfolge [34] relaxieren. Kommt man zu Knoten v, sind alle Kanten, die in v hineinführen, schon von ihren Vorgängern relaxiert worden. distTo[v] ist also bereits endgültig, bevor v seine eigenen Kanten weitergibt.

Der Code:

• distTo und edgeTo wie bei Dijkstra, Anfang unendlich, distTo[s] = 0.
• Topological aus Algorithmus 4.5, hier für kantengewichtete Digraphen überladen.
• Dann einfach: für jeden Knoten in topologischer Reihenfolge relax(G, v). Fertig.
• Keine Vorrangwarteschlange, kein marked[]. Jeder Knoten und jede Kante wird genau einmal angefasst, ein Knoten wird nie ein zweites Mal relaxiert.

Abbildung 4.77 (tinyEWDAG.txt, Start 5), topologische Ordnung 5 1 3 6 4 7 0 2:

Ergebnis (Testlauf):

Man sieht gut, dass Kanten vorläufig in den Baum kommen und später ersetzt werden (6→0, 6→2). Bei Dijkstra wäre das nicht passiert, weil er nach Abstand und nicht nach topologischer Ordnung vorgeht. Das Ergebnis ist dasselbe.

Satz S: In einem kantengewichteten DAG findet dieses Verfahren die kürzesten Pfade in Zeit proportional zu E + V, also linear. Gewichte dürfen negativ sein, weil die Korrektheit nur von der Reihenfolge abhängt, nicht vom Vorzeichen.

Längste Pfade gibt es gratis dazu: Alle Gewichte negieren, kürzeste Pfade berechnen, Vorzeichen zurückdrehen. Das ist der kürzeste Pfad der negierten Kopie und zugleich der längste im Original. In Graphen mit Zyklen ist das Längste-Pfade-Problem dagegen schwer, im DAG ist es linear. Anwendung im Buch kurz danach: die Methode des kritischen Pfads für Ablaufplanung mit Dauern, etwa im Projektmanagement. Der längste Pfad durch die Aufgaben bestimmt die Mindestdauer des Projekts.

Vergleich der Kürzeste-Pfade-Verfahren bisher:

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]
• Algorithmus 4.10: Kürzeste Pfade in azyklischen Digraphen [41]