Negative Kanten: Bellman-Ford und Floyd-Warshall
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 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 und die Kanten : , : , : , : , : , : . Gesucht sind die billigsten Wege von 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 für die Zahl der Knoten und für die Zahl der Kanten.
Dijkstra setzt von aus , und erklärt dann für fertig. Ist wirklich der Abstand von nach ?
Dijkstra auf dem Liefergraphen
Dijkstra auf dem Liefergraphen
Dijkstra arbeitet wie gewohnt; bei Gleichstand nehmen wir den alphabetisch ersten Knoten.
Schritt 1: fertig mit . Entspannen: , .
Schritt 2: fertig mit . Entspannen: .
Schritt 3: fertig mit (Gleichstand mit ). Die Kante führt zu einem fertigen Knoten und wird übergangen, obwohl wäre. Entspannen: .
Schritt 4: fertig mit . Entspannen: .
Schritt 5: fertig mit .
| Knoten | Dijkstra | wahrer Abstand | kürzester Weg |
|---|---|---|---|
Dijkstras Begründung: Jeder andere Weg zu passiert einen offenen Knoten mit , und das Reststück von nach kostet mindestens . Hier kostet das Reststück aber . Der falsche Wert bei vererbt sich auf und .
Alle Gewichte um eine Konstante anheben
Alle Gewichte um eine Konstante anheben
Man addiert zu jedem Gewicht ; dann ist alles nichtnegativ, und Dijkstra darf laufen. Mit den neuen Gewichten ist mit der kürzeste Weg nach . Im ursprünglichen Graphen kostet er aber , nicht .
Ein Weg mit Kanten wird um teurer, Wege mit vielen Kanten werden stärker bestraft. Der wahre kürzeste Weg hat vier Kanten und kostet nach der Verschiebung . Eine Konstante pro Kante ist keine zulässige Umformung.
Einfacher Weg, Kreis und negativer Kreis
Ein Weg heißt einfach, wenn kein Knoten zweimal vorkommt. Ein einfacher Weg hat höchstens Knoten und daher höchstens Kanten.
Ein Kreis in einem gerichteten Graphen ist ein Weg mit mindestens einer Kante, der an seinem Anfangsknoten endet, etwa . Ist die Summe seiner Gewichte negativ, heißt er negativer Kreis.
Wir schreiben für das kleinste Gewicht eines Weges von nach (Abstand) und , wenn es keinen Weg gibt.
Gegenbeispiel: Führt von ein Weg über einen negativen Kreis nach , gibt es kein kleinstes Gewicht, denn jede weitere Runde durch den Kreis macht den Weg billiger. Man setzt .
Ohne negative Kreise genügen einfache Wege
Ist von aus kein negativer Kreis erreichbar und ist von aus erreichbar, dann gibt es einen kürzesten Weg von nach , der einfach ist und damit höchstens Kanten hat.
Sei ein Weg von nach . Kommt ein Knoten zweimal vor, ist das Stück zwischen den beiden Vorkommen ein von aus erreichbarer Kreis, nach Voraussetzung nicht negativ. Herausgeschnitten bleibt ein Weg von nach mit weniger Kanten und höchstens dem Gewicht von . Wiederholen, bis kein Knoten doppelt vorkommt.
Zu jedem Weg gibt es also einen einfachen, der höchstens so viel wiegt. Von den endlich vielen einfachen Wegen hat einer das kleinste Gewicht; er ist ein kürzester Weg überhaupt.
Relaxation und Algorithmus von Bellman-Ford
Jeder Knoten trägt einen vorläufigen Wert und einen Vorgänger . Eine Kante relaxieren (entspannen) heißt: Ist , so setze auf diesen kleineren Wert und . Dabei gilt .
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 Kanten, Runden lang. Eine letzte Prüfrunde erkennt negative Kreise.
| Zeile | Einrückung | Anweisung |
|---|---|---|
| 1 | 0 | |
| 2 | 1 | |
| 3 | 1 | |
| 4 | 1 | |
| 5 | 2 | |
| 6 | 3 | |
| 7 | 4 | |
| 8 | 1 | |
| 9 | 2 | |
| 10 | 3 | |
| 11 | 1 |
Laufzeit: Zeile 2 kostet , jede der Runden , die Prüfrunde . Zusammen .
Bellman-Ford auf dem Liefergraphen
Bellman-Ford auf dem Liefergraphen
Die Kanten werden in jeder Runde in der Reihenfolge , , , , , relaxiert. Die Tabelle zeigt die Werte am Ende jeder Runde.
| Runde | |||||
|---|---|---|---|---|---|
| Start | |||||
| 1 | |||||
| 2 | |||||
| 3 |
In Runde 1 wird erst , dann (über ). bekommt aber schon vorher , weil vor drankommt. Erst Runde 2 reicht den besseren Wert an und weiter.
Runde 3 ändert nichts, also ändern auch alle weiteren Runden nichts (sie rechnen mit denselben Werten dasselbe). Man darf vor den Runden aufhören. Die Vorgänger ergeben den Weg mit Gewicht .
Probier es aus
Korrektheit von Bellman-Ford
Für jeden Knoten gilt zu jedem Zeitpunkt:
(a) ist oder das Gewicht eines Weges von nach .
(b) Nach Runde ist höchstens so groß wie das Gewicht jedes Weges von nach mit höchstens Kanten.
Ist von aus kein negativer Kreis erreichbar, so gilt nach Runden für alle .
Beweisidee: (a) Die Werte sind nie zu klein. (b) Nach Runden sind alle Wege mit höchstens Kanten berücksichtigt.
(a) Am Anfang ist , das Gewicht des Weges ohne Kante, sonst . Eine Änderung setzt mit endlichem : das Gewicht eines Weges nach , verlängert um .
(b) Induktion über ; Werte werden nur kleiner. Für gibt es nur den Weg ohne Kante von nach , und gilt von Anfang an.
Schritt : Sei ein Weg nach mit höchstens Kanten. Mit höchstens Kanten folgt alles aus der Annahme. Sonst sei die letzte Kante und das Anfangsstück bis mit Kanten. Am Ende von Runde ist . In Runde wird relaxiert, danach gilt .
Schluss: Ist erreichbar, gibt es nach dem vorigen Satz einen kürzesten Weg mit höchstens Kanten, also nach (b) und nach (a). Sonst bleibt nach (a).
Erkennen negativer Kreise
Nach den Runden gibt es genau dann eine Kante mit , wenn von aus ein negativer Kreis erreichbar ist.
Ohne erreichbaren negativen Kreis ist , und für jede Kante gilt : Ein kürzester Weg nach , dann , ist ein Weg nach . Also verbessert keine Kante.
Sei umgekehrt ein erreichbarer negativer Kreis, und angenommen, keine Kante verbessert: für . Die Werte auf dem Kreis sind endlich, denn nach (b) ist höchstens das Gewicht eines einfachen Weges nach . Summiert man über , steht links und rechts dieselbe Summe der Werte, also , ein Widerspruch.
Gerichteter Graph mit : , : , : , : , : , : . Nach vier Runden ist und . Welches Gewicht hat der Kreis ?
Floyd-Warshall: kürzeste Wege zwischen allen Paaren
Für eine ganze Entfernungstabelle kostet Bellman-Ford von jedem Knoten aus , bei in der Größenordnung also . Floyd-Warshall schafft mit dynamischer Programmierung: kleinere Teilprobleme lösen, ihre Lösungen in einer Tabelle speichern und daraus größere zusammensetzen.
Die Knoten heißen . Die inneren Knoten eines Weges sind alle außer Anfang und Ende. Das Teilproblem ist:
= kleinstes Gewicht eines Weges von nach , dessen innere Knoten alle in liegen.
Für sind keine inneren Knoten erlaubt: , , wenn es die Kante gibt, sonst . Für ist jeder Weg erlaubt, also .
Rekurrenz von Floyd-Warshall
Enthält der Graph keinen negativen Kreis, so gilt die Rekurrenz oben für alle und alle .
Wie im ersten Satz darf man sich auf einfache Wege beschränken; das Herausschneiden eines Kreises entfernt nur Knoten.
Höchstens das Minimum: Ein Weg mit inneren Knoten in ist auch einer mit inneren Knoten in , ebenso ein Weg von nach , gefolgt von einem von nach , beide mit inneren Knoten in .
Mindestens das Minimum: Sei ein kürzester einfacher Weg von nach mit inneren Knoten in . Ist kein innerer Knoten, gilt . Sonst kommt genau einmal vor, und zerfällt in Stücke und mit inneren Knoten in , also .
Floyd-Warshall mit vier Knoten
Floyd-Warshall mit vier Knoten
Kanten: : , : , : , : , : , : . Zeile , Spalte ist . Die Starttabelle enthält nur die Kanten:
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | ||||
| 2 | ||||
| 3 | ||||
| 4 |
: Nur Zeile hat einen endlichen Eintrag in Spalte . , .
: , .
: , , .
: , , .
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | ||||
| 2 | ||||
| 3 | ||||
| 4 |
gehört zum Weg ; er entsteht erst bei , weil er durch führt. Die Diagonale ist : kein negativer Kreis.
Die Schleife über k innen statt außen
Die Schleife über k innen statt außen
Man schreibt die Schleifen in der Reihenfolge : Für jedes Paar probiert man alle Zwischenknoten .
Dann wird festgelegt, bevor und fertig sind, und Wege mit mehreren Zwischenknoten werden übersehen. Die Rekurrenz verlangt, dass Stufe vollständig ist, bevor Stufe beginnt: Die Schleife über steht außen.
Laufzeiten im Vergleich
Laufzeiten im Vergleich
| Verfahren | Aufgabe | negative Gewichte | Laufzeit |
|---|---|---|---|
| Breitensuche | ein Start, ohne Gewichte | entfällt | |
| Dijkstra mit Heap | ein Start | nein | |
| Bellman-Ford | ein Start | ja, erkennt negative Kreise | |
| -mal Dijkstra | alle Paare | nein | |
| Floyd-Warshall | alle Paare | ja, erkennt negative Kreise |
Bei wenigen Kanten und nichtnegativen Gewichten ist -mal Dijkstra schneller als Floyd-Warshall, bei vielen Kanten nicht.
Du brauchst die Entfernungstabelle für Orte mit 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 Kanten.
Bellman-Ford relaxiert Runden lang alle Kanten; nach Runde sind alle Wege mit höchstens Kanten berücksichtigt. Laufzeit .
Verbessert nach Runden noch eine Kante, ist von aus ein negativer Kreis erreichbar.
Floyd-Warshall füllt mit der Rekurrenz ; die Schleife über steht außen. Laufzeit .
Ein negativer Diagonaleintrag am Ende zeigt einen negativen Kreis.
Übungen
Ein gerichteter Graph hat Knoten und Kanten. Wie viele Kantenprüfungen macht Bellman-Ford ohne vorzeitiges Aufhören, die Prüfrunde auf negative Kreise eingeschlossen?
Warum genügen bei Bellman-Ford Runden, wenn kein negativer Kreis erreichbar ist?
Gerichteter Graph: : , : , : , : , : , : , : , : , : . Bestimme mit Bellman-Ford den Abstand .
Im Floyd-Warshall-Beispiel der Lektion (Kanten : , : , : , : , : , : ): Welchen Wert hat , also das kleinste Gewicht eines Weges von nach mit inneren Knoten nur aus ?
Floyd-Warshall endet mit . Was folgt daraus?
Beweise: Ändert sich in einer Runde von Bellman-Ford kein einziger Wert, dann ist von aus kein negativer Kreis erreichbar, und alle Werte sind bereits die Abstände .