Bellman-Ford mit Warteschlange (Algorithmus 4.11)

So geht’s: Beim Öffnen läuft der Testclient mit tinyEWDn und Start s = 0 wie in Abbildung 4.91: derselbe Digraph wie bei Dijkstra, aber die drei Kanten aus 6 sind negativ. Rechts stehen edgeTo[], distTo[] und onQ[], darunter die Warteschlange (links wird entnommen, rechts eingereiht, darunter der Durchlauf). Der Knoten, dessen Kanten gerade relaxiert werden, ist orange. Rot umrandet sind die Knoten in der Warteschlange, grün alle, zu denen schon ein Weg bekannt ist. Die gerade geprüfte Kante ist blau gestrichelt, schwarz sind die Kanten in edgeTo[], grau gestrichelt die nicht auswählbaren. Wird ein Abstand durch eine negative Kante kleiner, sind die Abstände dahinter „nicht länger gültig“, sie stehen dann durchgestrichen in der Tabelle, bis ein späterer Durchlauf sie korrigiert. Bei jedem V-ten relax-Aufruf prüft findNegativeCycle() die Kanten aus edgeTo[] auf einen Zyklus. „tinyEWDnc“ zeigt den Fall aus Abbildung 4.92, bei dem 4→5→4 ein negativer Zyklus ist: Er wird rot, die Schleife bricht ab, und main() gibt den Zyklus aus. „ab s“ startet von einem anderen Knoten aus, „Zufallsgraph“ erzeugt einen neuen Digraphen mit negativen Gewichten, manchmal auch mit negativem Zyklus, „↺ Neu starten“ springt zurück zu tinyEWDn.

Erklärung

Bellman-Ford, warteschlangenbasiert (Algorithmus 4.11), Klasse BellmanFordSP. Das allgemeinste Kürzeste-Pfade-Verfahren: beliebige Digraphen, auch mit Zyklen, und auch mit negativen Gewichten.

Das Problem mit negativen Gewichten:

• Dijkstra [39] versagt, weil ein schon als endgültig entnommener Knoten später über eine negative Kante doch noch billiger erreichbar sein kann.
• Schlimmer: ein negativer Zyklus, also ein Kreis, dessen Gewichtssumme negativ ist. Läuft man ihn immer wieder, wird der Pfad beliebig kurz. Kürzeste Pfade sind dann für alle Knoten, die über diesen Zyklus erreichbar sind, gar nicht definiert.
• Bellman-Ford findet entweder die kürzesten Pfade oder meldet einen negativen Zyklus.

Grundidee Bellman-Ford: V Durchläufe, in jedem alle Kanten relaxieren. Nach k Durchläufen sind alle kürzesten Pfade mit höchstens k Kanten richtig. Ein kürzester Pfad ohne Zyklus hat höchstens V − 1 Kanten, also reichen V Durchläufe. Kostet E · V.

Die Verbesserung mit Warteschlange: Die meisten Relaxierungen bringen nichts. Eine Kante v→w kann nur dann etwas verbessern, wenn sich distTo[v] im letzten Durchgang geändert hat. Also merkt man sich nur diese Knoten in einer Warteschlange [16].

Der Code:

• distTo, edgeTo wie gehabt.
• queue: Knoten, deren Kanten noch relaxiert werden müssen.
• onQ[]: Steht der Knoten schon in der Schlange? Verhindert Duplikate.
• cost: zählt die relax-Aufrufe.
• cycle: speichert einen gefundenen negativen Zyklus.
• Start: s einreihen. Dann solange die Schlange nicht leer ist und kein negativer Zyklus gefunden wurde: Knoten herausnehmen, onQ zurücksetzen, relaxieren.

relax (Listing 4.36, hier nicht abgedruckt):

• Wie bei Dijkstra: Ist distTo[v] + Gewicht < distTo[w], dann distTo[w] und edgeTo[w] aktualisieren.
• Neu: w nur dann einreihen, wenn es nicht schon drin ist (onQ).
• Nach jeweils V Aufrufen wird findNegativeCycle() angestoßen.

Negative Zyklen finden (Listing 4.38):

• Aus den aktuellen edgeTo-Kanten wird ein Hilfsgraph gebaut und per Tiefensuche auf einen Zyklus geprüft, mit derselben onStack-Technik wie bei DirectedCycle [34].
• Ohne negativen Zyklus ist edgeTo immer ein Baum. Taucht darin ein Zyklus auf, muss er negativ sein.
• Ohne diese Prüfung würde der Algorithmus bei einem negativen Zyklus endlos laufen, weil sich die Abstände immer weiter verringern.

Satz W: Die warteschlangenbasierte Version braucht im schlimmsten Fall Zeit proportional zu E · V und Zusatzspeicher proportional zu V. In der Praxis ist sie meist deutlich schneller, oft nahe E + V.

Anwendung im Buch: Arbitrage. Wechselkurse als Graph: Knoten sind Währungen, Kanten Umtauschkurse. Nimmt man als Gewicht den negativen Logarithmus des Kurses, wird aus Multiplizieren ein Addieren. Ein negativer Zyklus bedeutet dann eine Umtauschkette, an deren Ende man mehr Geld hat als am Anfang.

Die drei Kürzeste-Pfade-Verfahren:

Faustregel: DAG → azyklisch. Keine negativen Gewichte → Dijkstra. Sonst Bellman-Ford.

Kapitel 4 komplett:

• 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]
• Algorithmus 4.11: Bellman-Ford [42]