Lektion 4.3

Negative Kanten: Bellman-Ford und Floyd-Warshall

40 min Lesezeit
Lesen anpassen

Nach dieser Lektion kannst du

  • an einem Gegenbeispiel zeigen, warum Dijkstra bei negativen Kantengewichten falsche Abstände liefert,

  • Bellman-Ford von Hand ausführen und per Induktion begründen, warum n−1n-1 Runden genügen,

  • mit einer zusätzlichen Prüfrunde einen negativen Kreis erkennen,

  • Floyd-Warshall als dynamische Programmierung über die Zwischenknoten aufschreiben und die Tabelle füllen,

  • die Laufzeiten der Verfahren vergleichen und für eine Aufgabe das passende wählen.

Vorausgesetzt: Graphen und Suche: Breitensuche und Tiefensuche, Kürzeste Wege mit dem Algorithmus von Dijkstra

Ein Lieferdienst plant Fahrten zwischen fünf Orten. Jede Fahrt kostet etwas, aber auf einer Strecke nimmt der Fahrer eine Rücklieferung mit und bekommt dafür mehr erstattet, als die Fahrt kostet. Diese Strecke hat also ein negatives Gewicht. Ähnlich gewinnt ein Elektroauto bergab Energie zurück.

Der Graph dazu ist gerichtet und hat die Knoten A,B,C,D,EA, B, C, D, E und die Kanten A→BA \to B: 22, A→CA \to C: 55, B→DB \to D: 33, C→BC \to B: −4-4, C→EC \to E: 66, D→ED \to E: 11. Gesucht sind die billigsten Wege von AA zu allen anderen Orten.

Dijkstra setzt nichtnegative Gewichte voraus. Diese Lektion zeigt, was ohne diese Voraussetzung schiefgeht, und stellt zwei Verfahren vor, die mit negativen Gewichten zurechtkommen: Bellman-Ford für einen Startknoten und Floyd-Warshall für alle Paare von Knoten. Wir schreiben n=∣V∣n = |V| für die Zahl der Knoten und m=∣E∣m = |E| für die Zahl der Kanten.

Vermute zuerst

Dijkstra setzt von AA aus dist(B)=2\text{dist}(B) = 2, dist(C)=5\text{dist}(C) = 5 und erklärt dann BB für fertig. Ist 22 wirklich der Abstand von AA nach BB?

Beispiel

Dijkstra auf dem Liefergraphen

Dijkstra arbeitet wie gewohnt; bei Gleichstand nehmen wir den alphabetisch ersten Knoten.

Schritt 1: AA fertig mit 00. Entspannen: dist(B)=2\text{dist}(B) = 2, dist(C)=5\text{dist}(C) = 5.
Schritt 2: BB fertig mit 22. Entspannen: dist(D)=2+3=5\text{dist}(D) = 2 + 3 = 5.
Schritt 3: CC fertig mit 55 (Gleichstand mit DD). Die Kante C→BC \to B führt zu einem fertigen Knoten und wird übergangen, obwohl 5+(−4)=1<25 + (-4) = 1 < 2 wäre. Entspannen: dist(E)=11\text{dist}(E) = 11.
Schritt 4: DD fertig mit 55. Entspannen: dist(E)=5+1=6\text{dist}(E) = 5 + 1 = 6.
Schritt 5: EE fertig mit 66.

KnotenDijkstrawahrer Abstandkürzester Weg
BB2211A,C,BA, C, B
CC5555A,CA, C
DD5544A,C,B,DA, C, B, D
EE6655A,C,B,D,EA, C, B, D, E

Dijkstras Begründung: Jeder andere Weg zu uu passiert einen offenen Knoten xx mit dist(x)≥dist(u)\text{dist}(x) \ge \text{dist}(u), und das Reststück von xx nach uu kostet mindestens 00. Hier kostet das Reststück C→BC \to B aber −4-4. Der falsche Wert bei BB vererbt sich auf DD und EE.

Häufige Fehler

Alle Gewichte um eine Konstante anheben

Man addiert zu jedem Gewicht 44; dann ist alles nichtnegativ, und Dijkstra darf laufen. Mit den neuen Gewichten 6,9,7,0,10,56, 9, 7, 0, 10, 5 ist A→B→D→EA \to B \to D \to E mit 6+7+5=186 + 7 + 5 = 18 der kürzeste Weg nach EE. Im ursprünglichen Graphen kostet er aber 66, nicht 55.

Richtig ist

Ein Weg mit kk Kanten wird um 4k4k teurer, Wege mit vielen Kanten werden stärker bestraft. Der wahre kürzeste Weg A,C,B,D,EA, C, B, D, E hat vier Kanten und kostet nach der Verschiebung 2121. Eine Konstante pro Kante ist keine zulässige Umformung.

Definition

Einfacher Weg, Kreis und negativer Kreis

Ein Weg heißt einfach, wenn kein Knoten zweimal vorkommt. Ein einfacher Weg hat höchstens nn Knoten und daher höchstens n−1n - 1 Kanten.

Ein Kreis in einem gerichteten Graphen ist ein Weg mit mindestens einer Kante, der an seinem Anfangsknoten endet, etwa B→C→D→BB \to C \to D \to B. Ist die Summe seiner Gewichte negativ, heißt er negativer Kreis.

Wir schreiben d(s,v)d(s, v) für das kleinste Gewicht eines Weges von ss nach vv (Abstand) und d(s,v)=∞d(s,v) = \infty, wenn es keinen Weg gibt.

Gegenbeispiel: Führt von ss ein Weg über einen negativen Kreis nach vv, gibt es kein kleinstes Gewicht, denn jede weitere Runde durch den Kreis macht den Weg billiger. Man setzt d(s,v)=−∞d(s, v) = -\infty.

Satz

Ohne negative Kreise genügen einfache Wege

Ist von ss aus kein negativer Kreis erreichbar und ist vv von ss aus erreichbar, dann gibt es einen kürzesten Weg von ss nach vv, der einfach ist und damit höchstens n−1n - 1 Kanten hat.

Definition

Relaxation und Algorithmus von Bellman-Ford

Jeder Knoten trägt einen vorläufigen Wert dist(v)\text{dist}(v) und einen Vorgänger vor(v)\text{vor}(v). Eine Kante (u,v)(u, v) relaxieren (entspannen) heißt: Ist dist(u)+w(u,v)<dist(v)\text{dist}(u) + w(u, v) < \text{dist}(v), so setze dist(v)\text{dist}(v) auf diesen kleineren Wert und vor(v)=u\text{vor}(v) = u. Dabei gilt ∞+w=∞\infty + w = \infty.

Dijkstra relaxiert die Kanten in einer klug gewählten Reihenfolge. Bellman-Ford (nach Richard Bellman und Lester Ford, 1950er-Jahre) verzichtet darauf: Es relaxiert in jeder Runde alle mm Kanten, n−1n - 1 Runden lang. Eine letzte Prüfrunde erkennt negative Kreise.

ZeileEinrückungAnweisung
10bellman_ford(G, w, s):\texttt{bellman\_ford(G, w, s):}
21for v in V: dist[v] = inf; vor[v] = None\texttt{for v in V: dist[v] = inf; vor[v] = None}
31dist[s] = 0\texttt{dist[s] = 0}
41for runde in 1, ..., n-1:\texttt{for runde in 1, ..., n-1:}
52for (u, v) in E:\texttt{for (u, v) in E:}
63if dist[u] + w(u, v) < dist[v]:\texttt{if dist[u] + w(u, v) < dist[v]:}
74dist[v] = dist[u] + w(u, v); vor[v] = u\texttt{dist[v] = dist[u] + w(u, v); vor[v] = u}
81for (u, v) in E:\texttt{for (u, v) in E:}
92if dist[u] + w(u, v) < dist[v]:\texttt{if dist[u] + w(u, v) < dist[v]:}
103return NEGATIVER_KREIS\texttt{return NEGATIVER\_KREIS}
111return dist, vor\texttt{return dist, vor}

Laufzeit: Zeile 2 kostet O(n)O(n), jede der n−1n - 1 Runden O(m)O(m), die Prüfrunde O(m)O(m). Zusammen O(n⋅m)O(n \cdot m).

dist(v)←min⁡(dist(v), dist(u)+w(u,v))\text{dist}(v) \leftarrow \min\bigl(\text{dist}(v),\ \text{dist}(u) + w(u,v)\bigr)
Beispiel

Bellman-Ford auf dem Liefergraphen

Die Kanten werden in jeder Runde in der Reihenfolge A→BA \to B, A→CA \to C, B→DB \to D, C→BC \to B, C→EC \to E, D→ED \to E relaxiert. Die Tabelle zeigt die Werte am Ende jeder Runde.

RundeAABBCCDDEE
Start00∞\infty∞\infty∞\infty∞\infty
10011555566
20011554455
30011554455

In Runde 1 wird BB erst 22, dann 11 (über C→BC \to B). DD bekommt aber schon vorher 2+3=52 + 3 = 5, weil B→DB \to D vor C→BC \to B drankommt. Erst Runde 2 reicht den besseren Wert an DD und EE weiter.

Runde 3 ändert nichts, also ändern auch alle weiteren Runden nichts (sie rechnen mit denselben Werten dasselbe). Man darf vor den n−1=4n - 1 = 4 Runden aufhören. Die Vorgänger ergeben den Weg A,C,B,D,EA, C, B, D, E mit Gewicht 55.

Bellman-Ford mit einer negativen Kante

Bellman-Ford · Negative Kante

Die Kante C → B hat das Gewicht −4, etwa eine Gutschrift. Dijkstra legt B zu früh fest und liegt deshalb bei B, D und E falsch; Bellman-Ford findet die richtigen Werte.

Gerichteter Graph · 5 Knoten · 6 Kanten

253−461Ad = 0StartBCDEZiel
Runden
0
Kanten geprüft
0
Verbesserungen
0
  • Kandidat
  • in Arbeit
  • fertig
  • kein kürzester Weg (−∞)
  • bester bekannter Weg
  • kürzester Weg
  • negativer Kreis
Schritt 1 von 24
Tempo
← → Schritt, Leertaste Abspielen
Start

Start bei A

Bellman-Ford findet kürzeste Wege auch bei negativen Gewichten. Statt Knoten der Reihe nach festzulegen, prüft es in jeder Runde alle Kanten: Ist über die Kante ein kürzerer Weg möglich, wird d verbessert. Ein kürzester Weg besucht keinen Knoten zweimal und hat darum höchstens n − 1 = 4 Kanten; nach so vielen Runden stimmen alle Abstände, falls kein Kreis mit negativer Summe im Spiel ist.

Datenstruktur

Gerade nicht in Gebrauch.

Werte der Knoten

KnotenZustanddvor
Awartet0–
Bunbekannt∞–
Cunbekannt∞–
Dunbekannt∞–
Eunbekannt∞–

d: Länge des besten bekannten Weges · vor: Vorgänger

Pseudocoden = 5, m = 6
  1. d[v] ← ∞, vor[v] ← – für alle v; d[s] ← 0
  2. wiederhole höchstens n − 1 Runden:
  3. für jede Kante u → v mit Gewicht w:
  4. wenn d[u] + w < d[v]: d[v] ← d[u] + w, vor[v] ← u
  5. hat sich in der Runde nichts geändert: fertig
  6. geht danach noch d[u] + w < d[v]: negativer Kreis
  7. alles, was von dort erreichbar ist: d ← −∞

Derselbe Graph wie im Text. Blättere Schritt für Schritt durch die Runden; die Tabelle unter dem Graphen zeigt d und vor für jeden Knoten, der Pseudocode die gerade ausgeführte Zeile.

Probier es aus

Satz

Korrektheit von Bellman-Ford

Für jeden Knoten vv gilt zu jedem Zeitpunkt:

(a) dist(v)\text{dist}(v) ist ∞\infty oder das Gewicht eines Weges von ss nach vv.
(b) Nach Runde ii ist dist(v)\text{dist}(v) höchstens so groß wie das Gewicht jedes Weges von ss nach vv mit höchstens ii Kanten.

Ist von ss aus kein negativer Kreis erreichbar, so gilt nach n−1n - 1 Runden dist(v)=d(s,v)\text{dist}(v) = d(s, v) für alle vv.

Satz

Erkennen negativer Kreise

Nach den n−1n - 1 Runden gibt es genau dann eine Kante (u,v)(u, v) mit dist(u)+w(u,v)<dist(v)\text{dist}(u) + w(u, v) < \text{dist}(v), wenn von ss aus ein negativer Kreis erreichbar ist.

Kurz geprüft

Gerichteter Graph mit A→BA \to B: 44, A→EA \to E: 1010, B→CB \to C: 33, C→DC \to D: −2-2, D→BD \to B: −3-3, D→ED \to E: 22. Nach vier Runden ist dist(B)=−4\text{dist}(B) = -4 und dist(C)=1\text{dist}(C) = 1. Welches Gewicht hat der Kreis B→C→D→BB \to C \to D \to B?

Definition

Floyd-Warshall: kürzeste Wege zwischen allen Paaren

Für eine ganze Entfernungstabelle kostet Bellman-Ford von jedem Knoten aus O(n2m)O(n^2 m), bei mm in der Größenordnung n2n^2 also O(n4)O(n^4). Floyd-Warshall schafft O(n3)O(n^3) mit dynamischer Programmierung: kleinere Teilprobleme lösen, ihre Lösungen in einer Tabelle speichern und daraus größere zusammensetzen.

Die Knoten heißen 1,2,…,n1, 2, \dots, n. Die inneren Knoten eines Weges sind alle außer Anfang und Ende. Das Teilproblem ist:

Dk[i][j]D_k[i][j] = kleinstes Gewicht eines Weges von ii nach jj, dessen innere Knoten alle in {1,…,k}\{1, \dots, k\} liegen.

Für k=0k = 0 sind keine inneren Knoten erlaubt: D0[i][i]=0D_0[i][i] = 0, D0[i][j]=w(i,j)D_0[i][j] = w(i, j), wenn es die Kante gibt, sonst ∞\infty. Für k=nk = n ist jeder Weg erlaubt, also Dn[i][j]=d(i,j)D_n[i][j] = d(i, j).

Dk[i][j]=min⁡(Dk−1[i][j], Dk−1[i][k]+Dk−1[k][j])D_k[i][j] = \min\bigl(D_{k-1}[i][j],\ D_{k-1}[i][k] + D_{k-1}[k][j]\bigr)
Satz

Rekurrenz von Floyd-Warshall

Enthält der Graph keinen negativen Kreis, so gilt die Rekurrenz oben für alle k=1,…,nk = 1, \dots, n und alle i,ji, j.

Beispiel

Floyd-Warshall mit vier Knoten

Kanten: 1→21 \to 2: 44, 1→31 \to 3: 11, 2→42 \to 4: 22, 3→23 \to 2: −2-2, 4→14 \to 1: 33, 4→34 \to 3: 55. Zeile ii, Spalte jj ist D[i][j]D[i][j]. Die Starttabelle D0D_0 enthält nur die Kanten:

D0D_01234
1004411∞\infty
2∞\infty00∞\infty22
3∞\infty−2-200∞\infty
433∞\infty5500

k=1k = 1: Nur Zeile 44 hat einen endlichen Eintrag in Spalte 11. D[4][2]=3+4=7D[4][2] = 3 + 4 = 7, D[4][3]=min⁡(5, 3+1)=4D[4][3] = \min(5,\ 3 + 1) = 4.
k=2k = 2: D[1][4]=4+2=6D[1][4] = 4 + 2 = 6, D[3][4]=−2+2=0D[3][4] = -2 + 2 = 0.
k=3k = 3: D[1][2]=min⁡(4, 1+(−2))=−1D[1][2] = \min(4,\ 1 + (-2)) = -1, D[1][4]=min⁡(6, 1+0)=1D[1][4] = \min(6,\ 1 + 0) = 1, D[4][2]=min⁡(7, 4+(−2))=2D[4][2] = \min(7,\ 4 + (-2)) = 2.
k=4k = 4: D[2][1]=2+3=5D[2][1] = 2 + 3 = 5, D[2][3]=2+4=6D[2][3] = 2 + 4 = 6, D[3][1]=0+3=3D[3][1] = 0 + 3 = 3.

D4D_41234
100−1-11111
255006622
333−2-20000
433224400

D4[2][3]=6D_4[2][3] = 6 gehört zum Weg 2→4→1→32 \to 4 \to 1 \to 3; er entsteht erst bei k=4k = 4, weil er durch 44 führt. Die Diagonale ist 00: kein negativer Kreis.

Häufige Fehler

Die Schleife über k innen statt außen

Man schreibt die Schleifen in der Reihenfolge i,j,ki, j, k: Für jedes Paar (i,j)(i, j) probiert man alle Zwischenknoten kk.

Richtig ist

Dann wird D[i][j]D[i][j] festgelegt, bevor D[i][k]D[i][k] und D[k][j]D[k][j] fertig sind, und Wege mit mehreren Zwischenknoten werden übersehen. Die Rekurrenz verlangt, dass Stufe k−1k-1 vollständig ist, bevor Stufe kk beginnt: Die Schleife über kk steht außen.

Beispiel

Laufzeiten im Vergleich

VerfahrenAufgabenegative GewichteLaufzeit
Breitensucheein Start, ohne GewichteentfälltO(n+m)O(n + m)
Dijkstra mit Heapein StartneinO((n+m)log⁡n)O((n + m)\log n)
Bellman-Fordein Startja, erkennt negative KreiseO(n⋅m)O(n \cdot m)
nn-mal Dijkstraalle PaareneinO(n(n+m)log⁡n)O(n(n + m)\log n)
Floyd-Warshallalle Paareja, erkennt negative KreiseO(n3)O(n^3)

Bei wenigen Kanten und nichtnegativen Gewichten ist nn-mal Dijkstra schneller als Floyd-Warshall, bei vielen Kanten nicht.

Kurz geprüft

Du brauchst die Entfernungstabelle für n=200n = 200 Orte mit m=30 000m = 30\,000 gerichteten Kanten, einige mit negativem Gewicht, aber ohne negativen Kreis. Welches Verfahren passt am besten?

Zusammenfassung

  • Dijkstra setzt nichtnegative Gewichte voraus: Ein zu früh festgelegter Wert wird nie korrigiert. Eine Konstante auf alle Gewichte zu addieren hilft nicht.

  • Ohne erreichbaren negativen Kreis gibt es einen einfachen kürzesten Weg mit höchstens n−1n-1 Kanten.

  • Bellman-Ford relaxiert n−1n-1 Runden lang alle Kanten; nach Runde ii sind alle Wege mit höchstens ii Kanten berücksichtigt. Laufzeit O(n⋅m)O(n \cdot m).

  • Verbessert nach n−1n-1 Runden noch eine Kante, ist von ss aus ein negativer Kreis erreichbar.

  • Floyd-Warshall füllt Dk[i][j]D_k[i][j] mit der Rekurrenz min⁡(Dk−1[i][j], Dk−1[i][k]+Dk−1[k][j])\min(D_{k-1}[i][j],\ D_{k-1}[i][k] + D_{k-1}[k][j]); die Schleife über kk steht außen. Laufzeit O(n3)O(n^3).

  • Ein negativer Diagonaleintrag D[v][v]D[v][v] am Ende zeigt einen negativen Kreis.

Übungen

Aufgabe 1Numerisch

Ein gerichteter Graph hat 88 Knoten und 1212 Kanten. Wie viele Kantenprüfungen macht Bellman-Ford ohne vorzeitiges Aufhören, die Prüfrunde auf negative Kreise eingeschlossen?

Aufgabe 2Multiple Choice

Warum genügen bei Bellman-Ford n−1n - 1 Runden, wenn kein negativer Kreis erreichbar ist?

Aufgabe 3Numerisch

Gerichteter Graph: S→AS \to A: 66, S→BS \to B: 77, A→CA \to C: 55, A→DA \to D: −4-4, B→CB \to C: −3-3, B→DB \to D: 99, C→AC \to A: −2-2, C→TC \to T: 33, D→TD \to T: 77. Bestimme mit Bellman-Ford den Abstand d(S,T)d(S, T).

Aufgabe 4Numerisch

Im Floyd-Warshall-Beispiel der Lektion (Kanten 1→21 \to 2: 44, 1→31 \to 3: 11, 2→42 \to 4: 22, 3→23 \to 2: −2-2, 4→14 \to 1: 33, 4→34 \to 3: 55): Welchen Wert hat D2[1][4]D_2[1][4], also das kleinste Gewicht eines Weges von 11 nach 44 mit inneren Knoten nur aus {1,2}\{1, 2\}?

Aufgabe 5Multiple Choice

Floyd-Warshall endet mit D[3][3]=−2D[3][3] = -2. Was folgt daraus?

Aufgabe 6Freitext

Beweise: Ändert sich in einer Runde von Bellman-Ford kein einziger Wert, dann ist von ss aus kein negativer Kreis erreichbar, und alle Werte sind bereits die Abstände d(s,v)d(s, v).