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 \rightarrow \R^+$ die günstigsten Wegen von einem Startknoten $s$ zu jedem anderen Knoten $v$ berechnet. Beachten Sie die Einschränkung $c: E \rightarrow \R^+$; Kantenkosten sind positiv. Macht es Sinn, Graphen mit beliebigen, also eventuell auch negativen Kantenkosten $c : E \rightarrow \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 $\Reached$ hinzugefügt), woraufhin dem bereits roten Nachbarn $z$ der Wert $\ETA(z)$ nach unten korrigiert wird. Zwar ist $\dist(s,z) = 0$, doch haben wir den Knoten $z$ schon zuvor der Menge $\Reached$ hinzugefügt, und zwar bei $t=2$. In der Analyse von Dijkstra haben wir ja gezeigt, dass $\dist(s,v) = \ETA(v)$ gilt für alle $v \in \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'$. Die Punkte behaupten:

Der Teilpfad $q_1$ von $s$ nach $v'$ ist ein günstigster Pfad von $s$ nach $v'$.
Es gilt $c(q) \geq c(q_1)$.

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

Behauptung*. Wenn $q_1$ ein Pfad von $s$ nach $v'$ ist und $q_2$ ein Pfad von $v'$ nach $v$, dann ist $q_1q_2$ ein Pfad von $s$ nach $v$ und $c(q) = c(q_1) + c(q_2)$.

Stimm das, auch wenn Kantenkosten negativ sind? Denken wir nach. Schreiben wir $q_1$ als $u_0, u_1, \dots u_k$ mit $u_0 = s$ und $u_k = v'$; schreiben wir $q_2$ als $u_k, u_{k+1}, \dots, u_l$ mit $u_l = v$. Dann ist $q = u_0, u_1, \dots, u_l$ und

\begin{align*} c(q) = \sum_{i=1}^l c(u_{i-1}, u_i) = \sum_{i=1}^k c(u_{i-1}, u_i) + \sum_{i=k+1}^l c(u_{i-1}, u_i) = c(q_1) + c(q_2) \ . \end{align*}

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

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

Lemma Sei $p_1$ ein Weg von $s$ nach $v$ und $p_2$ ein Weg von $v$ nach $t$. Dann ist $p_1p_2$ ein Weg von $s$ nach $t$ und \begin{align*} c(p_1p_2) = c(p_1) + c(p_2) \ . \end{align*}

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

Frage Stimmt es, dass es unter den günstigsten Wegen immer einen gibt, der ein Pfad ist?

Beweis / Gegenbeispiel. Sei $p$ ein günstigster Weg von $s$ nach $t$. Sei $p$ von all den günstigsten Wegen einer mit der kleinsten Anzahl von Kanten. Weil $p$ ja kein Pfad ist, gibt es einen Knoten $v$, der doppelt vorkommt (möglicherweise ist $v=s$ oder $v=t$, möglicherweise aber auch keines davon). Wir schreiben also

\begin{align*} s \stackrel{p}{\rightsquigarrow} t = s \stackrel{p_1}\rightsquigarrow v \stackrel{p_2} \rightsquigarrow v \stackrel{p_3} \rightsquigarrow t \end{align*}

Hierbei ist $p_2$ ein geschlossener Weg von $v$ zu sich selbst mit mindestens einer Kante. Was geschieht, wenn wir diesen geschlossenen Weg ausschneiden, alos $p' := p_1 p_3$ setzen?

Falls $c(p_2) = 0$ ist, dann ist $c(p') = c(p)$. Dies widerspricht der Tatsache, dass wir $p$ unter allen günstigsten Wegen so ausgesucht haben, dass es auch noch die wenigsten Kanten hat.
Falls $c(p_2) \gt 0$ ist, dann ist $c(p') \lt c(p)$ und es gibt einen noch günstigeren. Wieder ein Widerspruch.
Falls $c(p_2) \lt 0$ ist, dann gibt es einen Kreis mit negativen Kosten.

Wenn es von $s$ nach $t$ also keinen günstigsten Weg gibt, der auch ein Pfad ist, dann gibt es einen Kreis mit negativen Kosten. Dann können wir allerdings den Kreis beliebig oft wiederholen:

\begin{align*} s \stackrel{p}{\rightsquigarrow} t = s \stackrel{p_1}\rightsquigarrow v \stackrel{p_2} \rightsquigarrow v \stackrel{p_2} \rightsquigarrow v \dots \stackrel{p_2} \rightsquigarrow v \stackrel{p_3} \rightsquigarrow t \end{align*}

und beliebig günstige Wege bauen. Es gäbe also strenggenommen gar keinen günstigsten Weg, sondern nur unendliche Folgen immer günstigerer Wege.

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

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

Definition Sei $i \in \N$. Wir definieren $d_k(v)$ als \begin{align*} \min \{ c(p) \ | \ p \textnormal{ ist ein Weg von $s$ nach $v$ mit höchstens $k$ Kanten }\} \ . \end{align*} Sollte es keinen solchen geben, setzen wir $d_k(v) = \infty$.

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

Lemma: es gilt $d_k(s) = 0$ für alle $k \in N$. Für $v \in V \setminus \{s\}$ gilt $d_0(v) = \infty$ und

\begin{align} d_k(v) = \min_{(u,v) \in E} (d_{k-1}(u) + c(u,v)) \ . \label{eqn-cheapest-walk} \end{align} für alle $k \geq 1$.

Beweis. Die Behauptungen $d_k(s) = 0$ und $d_0(v)$ gelten offensichtlich. Für $k \geq 1$ zeigen wir nun dass sowohl $d_k(v) \leq \min_{(u,v) \in E} (d_{k-1}(u) + c(u,v))$ als auch $d_k(v) \geq \min_{(u,v) \in E} (d_{k-1}(u) + c(u,v))$ gelten.

Behauptung 1: $d_k(v) \leq \min_{(u,v) \in E} (d_{k-1}(u) + c(u,v))$.

Beweis. Wir zeigen, dass $d_k(v) \leq d_{k-1}(u) + c(u,v)$ für jeden Rein-Nachbarn $u$ individuell gilt. Wenn $d_{k-1}(u)=\infty$, dann gilt sie trivialerweise. Ansonsten gibt es einen Weg $p$ von $s$ nach $u$ mit höchstens $k-1$ Kanten und $c(p) = d_{k-1}(u)$. Fügen wir die Kante $c(u,v)$ hinzu, ergibt sich ein Weg $p'$ von $s$ nach $v$ mit höchstens $k$ Kanten und Kosten $c(p') = c(p) + c(u,v) = d_{k-1}(u) + c(u,v)$. Der optimale Weg von $s$ nach $v$ kann nur besser sein. Daher gilt die Ungleichung.

Behauptung 2: $d_k(v) \geq \min_{(u,v) \in E} (d_{k-1}(u) + c(u,v))$.

Beweis. Wieder unterscheiden wir zwei Fälle. Wenn $d_k(v) = \infty$ ist, dann gilt die Behauptung trivialerweise. Ansonsten sei $p$ ein günstigster Weg von $s$ nach $v$ der Länge höchstens $k$. Nach Definition gilt $d_k(v) = c(p)$. Sei $u$ der Vorgänger von $v$ auf diesem Weg und $p'$ der Weg $p$ ohne die letzte Kante. Der Weg $p'$ hat höchstens $k-1$ Kanten und daher gilt $d_{k-1} (u) \leq c(p')$ und somit auch

\begin{align*} d_k(v) = c(p) = c(p') + c(u,v) \geq d_{k-1}(u) + c(u,v) \geq \min_{(u,v) \in E} (d_{k-1}(u) + c(u,v)) \ . \end{align*}

Aus Behauptung 1 und 2 foglt (\ref{eqn-cheapest-walk}) und somit das Lemma. $\square$

Aus dem Lemma ergibt sich folgender iterativer Algorithmus:

def AlmostBellmanFord ($G = (V,E)$, $c : V \rightarrow \R^+$, $s \in V$, $T \in \N$)
1. $d_0(s) := 0$, $d_0(v) := \infty$ für alle $v \in V \setminus \{s\}$
2. for $i := 1, \dots, T$
  1. $d_i(s) = 0$
  2. for $v \in V:$
    1. $d_i(v) := \min \{ d_{i-1}(u) + c(u,v) \ | \ (u,v) \in E \}$

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

Algorithmus (AlmostBellmanFord). Dies ist noch kein richtiger Algorithmus, weil wir nicht spezifiziert haben, wie oft die äußere Schleife durchlaufen werden soll.

def AlmostBellmanFord ($G = (V,E)$, $c : V \rightarrow \R^+$, $s \in V$, $T \in \N$)
1. $d_0(s) := 0$, $d_0(v) := \infty$ für alle $v \in V \setminus \{s\}$
2. for $i := 1, \dots, T$
  1. $d_i(s) := 0$ und $d_i(v) := \infty$ für alle $v \in V \setminus \{s\}
  2. for $(u,v) \in E:$
    1. $d' := d_{i-1}(u) + c(u,v)$ // Alternativkosten für Weg via $u$
    2. if $d' \lt d_i(v)$:

Beobachtung Algorithmus 7.6 (AlmostBellmanFord) berechnet $\vec{d}_0, \vec{d}_1, \dots, \vec{d}_T$ in Zeit $O(mT)$.

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

Definition (günstigste Wege). Für jeden Knoten $v$ und jedes $i \geq 0$ ist $d_i(v) \in \R \cup \{+ \infty\}$ definiert. Wir definieren

\begin{align*} d(v) := \inf_{i \in \N} d_i(v) \ . \end{align*}

Wir sehen: $d(v) \in \R \cup \{-\infty, \infty\}$.

Das Infimum kann $-\infty$ 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:

Lemma Wenn $d(v) \in R$, dann gibt es einen Pfad $p$ von $s$ nach $t$ mit $c(p) = d(v)$.

Fehlerhafter Beweis. Wir betrachten alle günstigsten Wege von $s$ nach $v$ (also Wege $q$ mit $c(q)= d(v)$) und aus dieser Menge einen Weg $q$ mit der kleinsten Anzahl von Kanten. Wenn $q$ kein Pfad ist, dann ist

\begin{align*} q: s \stackrel{q_1}{\rightsquigarrow} z \stackrel{q_2}{\rightsquigarrow} z \stackrel{q_3}{\rightsquigarrow} v \ , \end{align*}

wobei $q_2$ ein geschlossener Weg von $z$ nach $z$ mit mindestens einer Kante ist. Wir betrachten nun drei Fälle:

Wenn $c(q_2) \lt 0$ gilt, dann können wir den Weg $q$ "aufblasen" und erhalten einen Weg $q_1 q_2 q_2 q_3$ mit kleineren Kosten. Dies widerspricht der Annahme, dass $q$ ein günstigster Weg war. Und insbesondere können wir $q_2$ beliebig oft wiederholen, was $d(v) = -\infty$ bedeutet. Dieser Falls kann also nach Annahme nicht eintreten.
Wenn $c(q_2) \gt 0$ gilt, dann können wir den Kreis ausscheniden und erhalten mit $q_1 q_3$ einen günstigeren Weg. Auch diese ist ein Widerspruch zur Annahme, dass $q$ ein günstiger Weg ist.
Wenn $c(q_2) = 0$ gilt, dann erhalten wir mit $q' := q_1 q_3$ einen Weg mit identischen Kosten. Der neue Weg $q'$ ist also auch ein günstigster Weg. Allerdings hat er weniger Kanten als $q$, was der Annahme entspricht, dass $q$ unter allen günstigsten Wegen ein kürzester ist.

In allen drei Fällen erhalten wir einen Widerspruch. Wir schließen: $q$ ist bereits ein Pfad.$\square$

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 $d(v) \in \R$ gilt, das $\inf$ in der Definition allerdings nie erreicht wird. Also wenn die Folge $d_0(v), d_1(v), \dots$ beispielsweise so aussieht:

\begin{align*} \infty, \infty, 2, \frac{3}{2}, \frac{4}{3}, \frac{5}{4}, \frac{6}{5}, \dots, \end{align*}

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

Korrekter Beweis. Sei $v$ ein Knoten mit $d(v) \in \R$. Wir können keinen "günstigsten" Weg wählen, eben weil wir nach dem obigen Konvergenz-Szenario gar nicht wissen, ob es so einen überhaupt gibt. Allerdings können wir folgendes zeigen:

Behauptung Zu jedem Weg $q$ von $s$ nach $v$ gibt es einen Pfad $p$ von $s$ nach $v$ mit $c(p) \leq c(q)$.

Beweis. Sei $q$ ein Weg von $s$ nach $v$ (nicht notwenigerweise ein günstigster). Wenn $q$ keinen Pfad hat, dann können wir wie im vorherigen Beweis den Kreis herausschneiden und einen neuen Pfad $q'$ erhalten mit $c(q') \leq c(q)$ (Fall 1 oben, dass der Kreis negative Kosten hat, ist ausgeschlossen; dann wäre, wie oben gesehen, $d(v) = -\infty$). Wir schneiden nun wiederholt Kreise aus bis wir einen Pfad $p$ erhalten haben. $\square$

Was nützt uns die Behauptung? Wenn es zu jedem Weg einen mindestens so guten Pfad gibt, dann können wir statt das Infimum über alle Wege zu nehmen das Infimum über alle Pfade nehmen:

\begin{align*} d(v) & = \inf_{i \in \N} d_i(v) \\ & = \inf_{i \in \N} \min \{c(q) \ | \ \textnormal{$q$ ist ein $s$-$v$-Weg mit $\leq i$ Kanten}\} \tag{Definition von $d_i$} \\ & = \inf_{i \in \N} \min \{c(q) \ | \ \textnormal{$q$ ist ein $s$-$v$-Pfad mit $\leq i$ Kanten}\} \tag{Behauptung 7.10} \\ & = \inf \{c(q) \ | \ \textnormal{$q$ ist ein $s$-$v$-Pfad}\} \end{align*}

Wir können nun das $\inf$ durch ein $\min$ ersetzen, weil es nur endlich viele Pfade gibt! Es gibt also einen günstigsten Pfad, und dieser hat Kosten $d(v)$. $\square$

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:

Lemma Wenn $d(v) \ne -\infty$ ist, dann ist $d(v) = d_{n-1}(v)$.

Beweis. Wenn $d(v) \in \R$, dann gibt es einen Pfad $p$ mit $c(p) = d(v)$. Da der Pfad $p$ höchstens $n-1$ Kanten hat, gilt also $c(p) = d_{n-1} (v)$. Wenn $d(v) = \infty$, dann gibt es keinen Weg von $s$ nach $v$ und somit ist auch $d_{n-1}(v) = \infty$.

$\square$

Es reicht also, AlmostBellmanFord bis $T = n$ laufen zu lassen.

Theorem $d(v) \ne -\infty \ \forall v \in V$ gilt genau dann, wenn $d_{n-1}(v) = d_n(v)\ \forall v \in V$ gilt.

In Worten: wenn sich bei AlmostBellmanFord im Schleifendurchlauf $i = n$ noch ein Wert ändert, dann gibt es einen negativen Kreis und Knoten $v$ mit $d(v) = -\infty$. Ansonsten erhalten wir mit $d_n(v)$ die korrekten Abstandswerte.

Beweis. Um eine Aussage $A$ genau dann, wenn $B$ zu beweisen, müssen wir immer zwei Dinge zeigen: $A \Rightarrow B$ und $B \Rightarrow A$. So auch hier.

Behauptung 1: $d(v) \ne -\infty \ \forall v \in V \Longrightarrow d_{n-1}(v) = d_n(v)\ \forall v \in V$.

Beweis: Nach Lemma 7.11 gilt nun $d(v) = d_{n-1}(v)$. Da $d_i$ nur sinken kann, bedeutet dies auch $d_n(v) = d_{n-1}(v)$.

Behauptung 2: $d_{n-1}(v) = d_n(v)\ \forall v \in V \Longrightarrow d(v) \ne -\infty \ \forall v \in V$.

Beweis: Der Algorithmus AlmostBellmanFord berechnet den Wertevektor $\vec{d}_{i+1}$ nur auf Basis von $\vec{d}_{i}$; ältere Werte $\vec{d_j}$ werden nicht benötigt. Formal: $\vec{d}_{i+1}$ ist eine Funktion von $\vec{d}_i$ (und $G$ und $s$ und $c$, natürlich). Wenn also $\vec{d}_{i+1} = \vec{d}_{i}$ gilt, dann auch $\vec{d}_{i+2} = \vec{d}_{i+1}$ und so bis in alle Ewigkeit. Wenn also $\vec{d}_{n} = \vec{d}_{n-1}$, dann gilt auch $\vec{d}_i = \vec{d}_{n-1}$ für alle $ i \geq n$ und somit auch $\inf_i d_i(v) = d_{n-1}(v)$. Letzteres ist nicht $-\infty$ und somit gilt die Behauptung.

Aus den beiden Behauptungen folgt nun das Lemma. $\square$

Wir können nun also AlmostBellmanFord für $T = n$ laufen lassen, dann nach Vollendung der Schleifen die Wertevektoren $\vec{d}_n$ und $\vec{d}_{n-1}$ vergleichen. Wenn sie identisch sind, können wir $\vec{d}_n$ 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 $d(v)$-Werte für jeden Knoten berechnen?

Wenn wir nun einen Knoten $v$ mit $d_n(v) \lt d_{n-1}(v)$ haben, dann bedeutet dies: der günstigste $s$-$v$-Weg $q$ mit bis zu $n$ Kanten ist besser als der günstigste mit bis zu $n-1$ Kanten. Also hat $q$ genau $n$ Kanten, ist somit kein Pfad sondern hat einen Kreis.

\begin{align*} q: s \stackrel{q_1}{\rightsquigarrow} z \stackrel{q_2}{\rightsquigarrow} z \stackrel{q_3}{\rightsquigarrow} v \ . \end{align*}

Der Kreis $q_2$ muss strikt negative Kosten haben, da sonst $q' := q_1 q_3$ mindestens so gut wäre - $c(q') \leq c(q) = d_n(v)$ - aber weniger Kanten hätte und somit von $d_{n-1}(v)$ mitgezählt worden wäre. Also: $q$ enthält einen negativen Kreis. Noch mehr: jeder Kreis, den $q$ enthält, hat strikt negative Kosten. Daher können wir mit folgendem Algorithmus einen negativen Kreis finden:

Algorithmus zum Finden negativer Kreise

Annahme: wir haben mit AlmostBellmanFord die Werte $\vec{d}_i$ und $\pred_i$ für $i = 0,\dots,n$ berechnet und es gibt ein $v \in V$ mit $d_n(v) \lt d_{n-1}(v)$
$u_n := v$
for $i = n...1$:
1. $u_{i-1} := \pred_{i}(u_i)$
$q:= [u_0, u_1, \dots, u_n]$ ist nun ein Pfad von $s$ nach $v$ mit $n$ Kanten und Kosten $d_n(v)$. Er enthält einen Kreis.
return einen beliebigen Kreis auf $q$

Wir können also feststellen, ob $G$ einen negativen Kreis enthält und, falls ja, einen solchen auch finden. Das reicht uns aber nicht: wir wollen $d(v)$ für jeden Knoten berechnen. Mittlerweile wissen wir: wenn $d_n(v) \lt d_{n-1}(v)$, dann gilt $d(v) = -\infty$. Die Gegenrichtung stimmt leider nicht: $d(v) = -\infty$ kann gelten auch wenn $d_n(v) = d_{n-1}(v)$ gilt. Das folgende Beispiel erläutert eine Fälle, auf die wir achten müssen:

Der Knoten $a$ liegt selbst nicht auf einem negativen Kreis, aber "flussabwärts", und somit ist $d(a) = -\infty$.
Die Knoten $e$ und $c$ dagegen liegen auf einem negativen Kreis, der allerdings nicht von $s$ aus erreichbar ist; somit ist $d(c) = d(e) = +\infty$.
Der Knoten $a$ hat zawr $d(a) = \infty$, allerdings gilt $d_1(a) = d_2(a) = \dots = d_{100}(a) = 500$. Der Wert beginnt erst dann zu sinken, wenn wir so oft den negativen Kreis abgelaufen sind, dass wir genügend $-2$ akkumuliert haben, um trotz der teuren 1000-Kante den direkten Weg $s-a$ über 500-Kante zu schlagen.

Das obige Beispiel, besonders Punkt 3, zeigt, dass $d_i(v)$ weit über $i=n$ hinaus stabil sein kann und dann dennoch abfällt und gegen $-\infty$ konvergiert. Dies geht aber nicht, wenn $v$ selbst auf einem negativen Kreis liegt:

Lemma Angenommen $v$ liegt auf einem negativen Kreis und ist von $s$ aus erreichbar. Dann gilt $d_{2n-1}(v) \lt d_{n-1}(v)$.

Beweis. Sei $q$ ein günstigster Kreis von $s$ nach $v$ mit höchstens $n-1$ Kanten und $q'$ ein negativer Kreis, der $v$ enthält. Also $c(q) = d_{n-1}(v)$ und $c(q') \lt 0$. Dann ist $qq'$ auch ein Weg von $s$ nach $v$ mit Kosten $c(qq') \lt c(q) = d_{n-1}(v)$. Der Kreis $q'$ hat höchstens $n$ Kanten; somit hat $qq'$ höchstens $2n-1$ viele und $d_{2n-1}(v) \leq c(qq')$. $\square$

Anmerkung: ich habe behauptet, dass der Kreis $q'$ höchstens $n$ Kanten hat. Das stimmt, allerdings nur, wenn wir Kreis streng interpretieren als geschlossenen Weg $u_0 u_1 u_2 \dots u_n$ auf welchem neben $u_0 = u_n$ kein Knoten doppelt vorkommt: $u_i \ne u_j$ für alle $1 \leq i \lt j \leq n$. 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 $d(v)$ für alle $v \in V$ berechnet:

Algorithmus (Bellman-Ford)

Verwende AlmostBellmanFord, um die Werte $d_i(v), \pred_i(v)$ für alle $i = 0,\dots,2n-1$ und $v \in V$ zu berechnen.
$X := \{v \in V \ | \ d_{2n-1}(v) \lt d_{n-1}(v)\}$ $X$ enthält alle Knoten, die auf einem von $s$ aus erreichbaren negativen Kreis liegen; und möglicherweise weitere Knoten.
$Y := \{w \in V \ | \ \textnormal{es gibt einen Pfad $v \rightsquigarrow w$}\}$
$d(v) := -\infty$ für alle $ v\in Y$
$d(v) := d_{n-1}(v)$ für alle $v \in V \setminus Y$