7. Graphen mit Kantenkosten

7.2 Kürzeste Wege mit positiven und negativen Kosten: der Bellman-Ford-Algorithmus

Im letzten Kapitel haben wir Dijkstras Algorithmus kennengelernt, der für einen Graphen $G=(V,E)$ mit Kantenkosten $c:E\to {\mathbb{R}}^{+}$ die günstigsten Wegen von einem Startknoten $s$ zu jedem anderen Knoten $v$ berechnet. Beachten Sie die Einschränkung $c:E\to {\mathbb{R}}^{+}$; Kantenkosten sind positiv. Macht es Sinn, Graphen mit beliebigen, also eventuell auch negativen Kantenkosten $c:E\to \mathbb{R}$ zu betrachten? Bei einer Navigations-App sicherlich nicht. Für Frachtschiffunternehmen dagegen schon: vielleicht verursacht die Strecke Singapur - Jakarta Kosten. Auf der Strecke Strecke Jakarta - Hong Kong dagegen können Sie Profit machen (also negative Kosten kassieren). Überzeugen wir uns zuerst einmal davon, dass Dijkstras Algorithmus an diesem Problem versagt.

Im Schritt $t=3$ geschieht etwas Ungeheuerliches: der Knoten $y$ wird rot gefäbrt (also der Menge $\text{Reached}$ hinzugefügt), woraufhin dem bereits roten Nachbarn $z$ der Wert $\text{ETA}(z)$ nach unten korrigiert wird. Zwar ist $\text{dist}(s,z)=0$, doch haben wir den Knoten $z$ schon zuvor der Menge $\text{Reached}$ hinzugefügt, und zwar bei $t=2$. In der Analyse von Dijkstra haben wir ja gezeigt, dass $\text{dist}(s,v)=\text{ETA}(v)$ gilt für alle $v\in \text{Reached}$: Punkt 1 von Lemma 7.2. Offensichtlich ist diese Behauptung für den Knoten $z$ zum Zeitpunkt $t=2$ verletzt. Woran scheitert der Beweis?

Schauen wir nochmals kritisch auf die Punkte 2 und 4 im Beweis von Behauptung 7.3. Zur Erinnerung: wir haben einen günstigsten Pfad $q$ von $s$ nach $v$ und auf diesem Pfad einen Knoten $v^{\prime }$. Die Punkte behaupten:

2. Der Teilpfad $q_1$ von $s$ nach $v^{\prime }$ ist ein günstigster Pfad von $s$ nach $v^{\prime }$.
4. Es gilt $c(q)\ge c(q_1)$.

Punkt 4 gilt offensichtlich nur, wenn der zweite Teil, also $$ von $$ nach $$, nichtnegative Kosten hat. In diesem Teilkapitel können wir also nicht davon ausgehen! Was ist mit Punkt 2? Argumentieren wir mit dem Kontrapositiv: wenn $$ kein günstigster Pfad von $$ nach $$ wäre, dann gäbe es einen günstigeren Pfad $$ mit $$. Dann wäre allerdings der Pfad $$ günstiger als $$, was der Annahme widerspräche, dass $$ der günstige ist. Die fundamentale Eigenschaft von Pfaden ist nämlich, dass man sie zusammenfügen kann:

Stimm das, auch wenn Kantenkosten negativ sind? Denken wir nach. Schreiben wir $$ als $$ mit $$ und $$; schreiben wir $$ als $$ mit $$. Dann ist $$ und

$$

Allerdings können wir uns nicht sicher sein, dass $$ ein Pfad ist! Es ist ja möglich, dass ein Knoten sowohl in $$ als auch in $$ vorkommt und somit zweimal in $$. Und violà gibt es ein Gegenbeispiel zu Punkt 2:

Der günstigste Pfad von $$ nach $$ ist $$ und hat Kosten $$. Der Teilpfad $$ hat Kosten $$. Allerdings gibt es einen noch günstigeren Pfad nach $$, nämlich $$ mit Kosten -10. Das obige Argument scheitert daran, dass die Verknüpfung $$ kein Pfad ist, weil $$ doppelt vorkommt. Ansonsten hätte $$ die Kosten -7, also günstiger als $$. Wir können die obige Behauptung* aber retten, wenn wir "Pfad" durch "Weg" ersetzen.

Im Ernstfall interessieren uns aber nur günstigste Wege. Und da sollte es ja nie Sinn machen, einen Knoten doppelt zu verwenden, oder?

Der Bellman-Ford-Algorithmus: Günstigste Wege und negative Kreise

Ein entscheidender Schritt wird sein, die Definition von $$ neu aufzurollen und statt Pfaden eben Wege zu betrachten. Zusätzlich zahlt es sich aus, die Länge dieser Wege mit zu betrachten.

Wir können die Werte $$ mit einem einfachen (leider jedoch nicht sehr effizienten) Algorithmus berechnen. Die entscheidende Beobachtung ist:

Aus dem Lemma ergibt sich folgender iterativer Algorithmus:

1. def AlmostBellmanFord ($$, $$, $$, $$)
   1. $$, $$ für alle $$
   2. for $$
      1. $$
      2. for $$
         1. $$

Da das Berechnen des Minimums in Zeile 6 oben wiederum eine Schleife über alle eingehenden Kanten bedeutet, formuliere ich den Algorithmus leicht um:

Wir können nun die günstigsten Wegekosten wie folgt formal definieren:

Das Infimum kann $$ werden, nämlich wenn es beliebig günstige Wege gibt (also mit immer stärker negativen Kosten). Das ist aber glücklicherweise alles, was schiefgehen kann:

Die Beweisstrategie, einen Repräsentanten zu wählen, der gewisse - scheinbar irrelevante - Parameter minimiert, wie hier die Anzahl der Kanten, ist eine recht übliche Methode. Allerdings ist obiger Beweis fehlerhaft. Haben Sie den Fehler entdeckt? Nun ja, es könne sein, dass $$ gilt, das $$ in der Definition allerdings nie erreicht wird. Also wenn die Folge $$ beispielsweise so aussieht:

$$

also gegen eine reelle Zahl (hier: 1) konvergiert, diese aber nie erreicht. Kann das geschehen? Nein, wie wir sehen werden:

Für diesen Beweis war es essentiell, dass "unendliche" Optimierungsproblem (bester Weg) durch das "endliche" Problem (bester Pfad) zu ersetzen, um das Infimum durch ein Minimum zu ersetzen. Wir wissen nun auch, bis wohin wir den Algorithmus AlmostBellmanFord laufen lassen müssen:

Es reicht also, AlmostBellmanFord bis $$ laufen zu lassen.

Wir können nun also AlmostBellmanFord für $$ laufen lassen, dann nach Vollendung der Schleifen die Wertevektoren $$ und $$ vergleichen. Wenn sie identisch sind, können wir $$ als Ergebnis ausgeben; wenn sie nicht identisch sind, können wir Error: graph contains negative cycle ausgeben. Es bleiben folgende Fragen:

• Wir wissen dann zwar, dass es einen negativen Kreis gibt. Wie aber finden wir ihn?
• Wie können wir die tatsächlichen $$-Werte für jeden Knoten berechnen?

Wenn wir nun einen Knoten $$ mit $$ haben, dann bedeutet dies: der günstigste $$-$$-Weg $$ mit bis zu $$ Kanten ist besser als der günstigste mit bis zu $$ Kanten. Also hat $$ genau $$ Kanten, ist somit kein Pfad sondern hat einen Kreis.

$$

Der Kreis $$ muss strikt negative Kosten haben, da sonst $$ mindestens so gut wäre - $$ - aber weniger Kanten hätte und somit von $$ mitgezählt worden wäre. Also: $$ enthält einen negativen Kreis. Noch mehr: jeder Kreis, den $$ enthält, hat strikt negative Kosten. Daher können wir mit folgendem Algorithmus einen negativen Kreis finden:

Wir können also feststellen, ob $$ einen negativen Kreis enthält und, falls ja, einen solchen auch finden. Das reicht uns aber nicht: wir wollen $$ für jeden Knoten berechnen. Mittlerweile wissen wir: wenn $$, dann gilt $$. Die Gegenrichtung stimmt leider nicht: $$ kann gelten auch wenn $$ gilt. Das folgende Beispiel erläutert eine Fälle, auf die wir achten müssen:

1. Der Knoten $$ liegt selbst nicht auf einem negativen Kreis, aber "flussabwärts", und somit ist $$.
2. Die Knoten $$ und $$ dagegen liegen auf einem negativen Kreis, der allerdings nicht von $$ aus erreichbar ist; somit ist $$.
3. Der Knoten $$ hat zawr $$, allerdings gilt $$. Der Wert beginnt erst dann zu sinken, wenn wir so oft den negativen Kreis abgelaufen sind, dass wir genügend $$ akkumuliert haben, um trotz der teuren 1000-Kante den direkten Weg $$ über 500-Kante zu schlagen.

Das obige Beispiel, besonders Punkt 3, zeigt, dass $$ weit über $$ hinaus stabil sein kann und dann dennoch abfällt und gegen $$ konvergiert. Dies geht aber nicht, wenn $$ selbst auf einem negativen Kreis liegt:

Anmerkung: ich habe behauptet, dass der Kreis $$ höchstens $$ Kanten hat. Das stimmt, allerdings nur, wenn wir Kreis streng interpretieren als geschlossenen Weg $$ auf welchem neben $$ kein Knoten doppelt vorkommt: $$ für alle $$. Nun sollten Sie Bauchweh bekommen: haben wir zuvor im Kapitel "Kreis" immer so interpretiert? Um die Bauchschmerzen loszuwerden, zeigen Sie doch, dass ein negativer geschlossener Weg immer einen negativen Kreis enthält.

Hier ist also unser endgültiger Algorithmus BellmanFord, der $$ für alle $$ berechnet: