Bellmann-Ford

Auf dieser Seite wird der Bellmann-Ford Algorithmus behandelt. Bei Dijkstra dürfen nur nichtnegative Gewichte benutzt werden. Doch gibt es auch eine Variante mit negativen Gewichten? Das würde nur bei gerichteten Graphen Sinn machen. Das Problem sind Zyklen mit negativem Gesamtgewicht. Ein Beispiel für Gewinn statt Kosten ist beispielsweise ein Verbindungsnetz mit Bonus Gewinnen für bestimmte Verbindungen um Auslastungen zu erhöhen. Dies ist bei Flügen mit Zwischenstopps der Fall, die oft billiger sind. Dieser Algorithmus löst ebenfalls das SSSP Problem.

Prinzip

Der Algorithmus erfolgt in mehreren Durchläufen. Es wird zunächst die bisher beste mögliche Verbindung bestimmtl, die die um eine Kante länger ist. Der i-te Durchlauf berechnet korrekt alle Pfade vom Startknoten der Länge i. Der längste Pfad ohne Zyklus hat eine Länge kleiner als |V|-1, somit hat man spätestens nach |V|-1 Durchläufen ein stabiles Ergebnis. Sollte das Ergebnis nach |V|-1 Durchläufen nicht stabil sein, so ist ein negativ bewerteter Zyklus enthalten. Hierbei wird das Prinzip der dynamischen Programmierung verwendet.

Algorithmus

algorithm BF(G, s)
   Eingabe: ein Graph G mit Startknoten s

   D[s] = 0
   D[t] = ∞ for all other t
   for i := 1 to |V|-1 do
      for each (u,v)∈ E do
         if D[u]+γ((u,v)) < D[v] then
            D[v] := D[u] + γ((u,v))
         fi
      od
   od

Beispiel

Bei der Initialisierung wird der Startknoten auf den Wert 0 gesetzt und alle weiteren Knoten erhalten den Wert ∞.

Beim ersten Schleifendurchlauf bekommt x den Wert 5 und u den Wert 10 zugewiesen.

Im zweiten Schleifendurchlauf werden alle weiteren Verbindungen aktualisiert, sowohl von u als auch von x. Dabei ändern sich die Werte von v, y und auch u. Die Änderung an u wird aber erst im nächsten Schritt an v propagiert.

Im dritten, i=3, Schleifendurchlauf verändern sich diesmal nur noch die Werte der Knoten v und y. Der neue Wert aus y berechnet sich durch den vorherigen Wert aus v=11 und der negativ gewichteten Kante -5. Hier wird also die negativ gewichtete Kante (v,y) zur Berechnung von D[y] genutzt.

Im vierten, i=4, Schleifendurchlauf wird nochmals die negativ gewichtete Kante (v,y) zur Berechnung von D[y] genutzt. Das Greedy-Verfahren, das jeden Knoten nur einmal besucht, hätte für y den in jedem Schritt lokal optimalen Pfas $<s,x,y>$ gewählt und nicht das beste Ergebnis geliefert.

Analyse

Terminierungstheorem

Der Algorithmus BF(G,s) terminiert für eine endliche Eingabe G in endlicher Zeit.

Beweis

Alle Schleifen sind endlich.

Korrektheitstheorem

Ist G ein Graph, der keinen Zyklus mit negativem Gewicht hat, so enthält D nach Aufruf BF(G,s) die Distanzwerte von s zu allen Knoten.

Beweis

Wir zeigen, dass die folgenden Aussagen Schleifeninvariante der for‐ Schleife (Schleifenvariable i) sind:

Ist D[v] < ∞, so ist D[v] der Wert eines Pfades von s nach v
Ist D[v] < ∞, so ist D[v] der kleinste Wert eines Pfades von s nach v mit maximal i Kanten
D[v] < ∞ gdw. es einen Pfad von s nach v mit gleich oder weniger als i Kanten gibt

Da G keine Zyklen mit negativem Gewicht hat, ist die Länge des längsten kürzesten Pfades maximal |Anzahl Knoten|‐1 (jeder Knoten wird auf diesem Pfad einmal besucht). Also gilt nach dem letzten Schleifendurchlauf nach 2 und 3. die Aussage des Theorems. Wir zeigen diese Aussagen durch Induktion nach i(=#Schleifendurchläufe).

Bei i=0 gilt vor dem ersten Schleifendurchlauf nur D[s]=0 < ∞. Daraus folgt direkt 1., 2., 3.
Bei i -> i+1 beweisen wir zunächst Aussage 3.
- War D[v] schon vorher endlich, so gilt die Aussage nach IV.
- Ist D[v] in diesem Schritt auf einen endlichen Wert gesetzt worden, so gab es ein u, so dass D[u] vorher schon endlich war und D[v]=D[u]+γ(u,v). Nach IV gibt es einen Pfad von s nach u der Länge i. Damit gibt es einen Pfad der Länge i+1 von s nach v.
- Umgekehrt wird bei Existenz eines Pfades der Länge i+1 dieser auch gefunden und D[v] auf einen endlichen Wert gesetzt.

Die Aussage 1 wird dadurch bewiesen, dass nach IV der Wert eines Pfades von s nach u D[u] ist. Wird D[v]=D[u]+γ(u,v) gesetzt so ist somit D[v] der Wert des Pfades von s nach v über u.
Die Aussage 2 wird dadurch bewiesen, dass nach IV der kleinste Wert eines Pfades von s nach v mit maximal i Kanten D[v] ist. Mache folgende Fallunterscheidung:
- 1.Fall: Es existiere ein Pfad P1 von s nach v mit i+1 Kanten, der minimalen Wert unter allen Pfaden von s nach v mit gleich oder weniger als i+1 Kanten hat. Betrachte den vorletzten Knoten u auf diesem Pfad und den Teilpfad P2 von P1 von s nach u. Dieser Teilpfad hat minimalen Wert unter allen Pfaden der maximalen Länge i von s nach u (ansonsten wäre P1 kein Pfad mit minimalem Wert). Nach IV ist D[u] genau dieser Wert und D[u]+γ(u,v) der Wert von P1, der dann im i+1ten Durchgang aktualisiert wird.
- 2.Fall: Es existiere kein Pfad von s nach v mit i+1 Kanten, der minimalen Wert unter allen Pfaden von s nach v mit gleich oder weniger als i+1 Kanten hat.
  - 1. Unterfall: Es existiert kein Pfad von s nach v mit maximal i+1 Kanten. Dann bleibt nach 3. D[v]=∞.
  - 2. Unterfall: Es existiert ein Pfad von s nach v mit k<i+1 Kanten, der minimalen Wert unter allen Pfaden von s nach v mit gleich oder weniger als i+1 Kanten hat. Dann ist nach IV D[v] genau dieser Wert und wird im i+1ten Durchgang auch nicht aktualisiert.

Graph mit negativ gewichtetem Zyklus

Betrachten wir die Situation nach |V|-1 Iterationen. Eine Kante könnte noch verbessert werden genau dann wenn der Graph einen Zyklus negativer Länge enthält. Der Zyklus s,x,u,v,y,s hat die Kosten 5+3+1-5-7=-3. Jeder Durchlauf durch den Zyklus erzeugt also einen Gewinn. Es gibt hier keinen günstigen Pfad endlicher Länge!

Laufzeittheorem

Sei G=(V,E,g) ein gerichteter Graph. Der Laufzeitaufwand vom Algorithmus von Bellmann‐Ford für einen beliebigen Knoten s in G ist O(|V||E|).

Beweis

Einfache Schleifenanalyse.