Der Algorithmus von Ford des Öffentlichen Ausrufers schätzt einzelne Quelle kürzeste Pfade in einem belasteten Digraph.

Für Graphen mit nur nichtnegativen Rand-Gewichten behebt der Algorithmus des schnelleren Dijkstras auch das Problem.

So wird Ford des Öffentlichen Ausrufers in erster Linie für Graphen mit negativen Rand-Gewichten verwendet.

Der Algorithmus wird nach seinen Entwicklern, Richard Bellman und Lester Ford dem Jüngeren genannt.

Wenn ein Graph einen "negativen Zyklus", d. h., ein Zyklus enthält, dessen Rand-Summe zu einem negativen Wert, dann können Spaziergänge des willkürlich niedrigen Gewichts gebaut werden, d. h., es keinen kürzesten Pfad geben kann. Ford des öffentlichen Ausrufers kann negative Zyklen entdecken und ihre Existenz melden, aber es kann keine richtige Antwort erzeugen, wenn ein negativer Zyklus von der Quelle nicht erreichbar ist.

Gemäß Robert Sedgewick, "Sind negative Gewichte nicht bloß eine mathematische Wissbegierde; [...] [sie] entstehen auf eine natürliche Weise, wenn wir andere Probleme auf Probleme der kürzesten Pfade reduzieren". Lassen Sie G ein Graph sein, der einen negativen Zyklus enthält. Eine NP-Complete Variante des Problems des kürzesten Pfads bittet um den kürzesten Pfad in G (einen negativen Zyklus enthaltend), solch, dass kein Rand wiederholt wird. Sedgewick gibt die Verminderung vom Pfad-Problem von Hamiltonian bis diese Variante des Problems.

Algorithmus

Ford des öffentlichen Ausrufers ist in seiner grundlegenden dem Algorithmus von Dijkstra sehr ähnlichen Struktur, aber anstatt den Knoten des minimalen Gewichts gierig auszuwählen, der noch nicht bearbeitet ist, um sich zu entspannen, entspannt es einfach alle Ränder, und tut diesen |V | − 1mal, wo |V | die Zahl von Scheitelpunkten im Graphen ist. Die Wiederholungen erlauben minimalen Entfernungen, sich überall im Graphen seitdem ohne negative Zyklen genau fortzupflanzen, der kürzeste Pfad kann nur jeden Knoten höchstens einmal besuchen. Verschieden von der gierigen Annäherung, die von bestimmten Strukturannahmen abhängt, ist auf positive Gewichte zurückzuführen gewesen, diese aufrichtige Annäherung streckt sich bis zu den allgemeinen Fall aus.

Ford des öffentlichen Ausrufers läuft in O (|V · |E) Zeit, wo |V und |E die Zahl von Scheitelpunkten und Rändern beziehungsweise sind.

Verfahren-BellmanFord (verzeichnen Scheitelpunkte, Listenränder, Scheitelpunkt-Quelle)

//Diese Durchführung nimmt in einem Graphen, vertreten als Listen von Scheitelpunkten

//und Ränder, und modifizieren die Scheitelpunkte so dass ihre Entfernung und

//Vorgänger schreibt zu versorgen die kürzesten Pfade.

//Schritt 1: Initialisieren Sie Graphen

für jeden Scheitelpunkt v in Scheitelpunkten:

wenn v Quelle dann v.distance ist: = 0

sonst v.distance: = Unendlichkeit

v.predecessor: = ungültiger

//Schritt 2: Entspannen Sie Ränder wiederholt

weil ich von 1 bis Größe (Scheitelpunkte)-1:

für jeden Rand uv in Rändern://ist uv der Rand von u bis v

u: = uv.source

v: = uv.destination

wenn u.distance + uv.weight und der Moment vorher für den Zyklus zum ersten Mal durchgeführt wird. Dann, für den Quellscheitelpunkt, der richtig ist. Für andere Scheitelpunkte u, der auch richtig ist, weil es keinen Pfad von der Quelle zu u mit 0 Rändern gibt.

Für den induktiven Fall beweisen wir zuerst den ersten Teil. Denken Sie einen Moment, wenn eine Entfernung eines Scheitelpunkts durch aktualisiert wird

. Durch die induktive Annahme, ist die Länge von einem Pfad von der Quelle zu u. Dann ist die Länge des Pfads von der Quelle zu v, der dem Pfad von der Quelle zu u folgt und dann zu v geht.

Für den zweiten Teil, denken Sie den kürzesten Pfad von der Quelle zu u mit höchstens mir Ränder. Lassen Sie v der letzte Scheitelpunkt vorher u auf diesem Pfad sein. Dann ist der Teil des Pfads von der Quelle zu v der kürzeste Pfad von der Quelle zu v mit an den meisten i-1 Rändern. Durch die induktive Annahme, danach i1 Zyklen ist höchstens die Länge dieses Pfads. Deshalb, ist höchstens die Länge des Pfads von s bis u. Im Ich-Zyklus, kommt im Vergleich dazu, und wird gleich ihm gesetzt, wenn kleiner war. Deshalb, nachdem ich Zyklen, höchstens die Länge des kürzesten Pfads von der Quelle zu u ist, der mich höchstens Ränder verwendet.

Wenn es keine Zyklen des negativen Gewichts gibt, dann besucht jeder kürzeste Pfad jeden Scheitelpunkt höchstens einmal, so am Schritt 3 können keine weiteren Verbesserungen gebildet werden. Nehmen Sie umgekehrt an, dass keine Verbesserung gebildet werden kann. Dann für jeden Zyklus mit Scheitelpunkten v [0]..., v [k1],

Um den Zyklus der v [ich].distance-Begriffe und der v [i1 (mod k)] resümierend, heben sich Entfernungsbegriffe auf, abreisend

D. h. jeder Zyklus hat nichtnegatives Gewicht.

Anwendungen in der Routenplanung

Eine verteilte Variante des Algorithmus von Ford des Öffentlichen Ausrufers wird in Entfernungsvektor-Routenplanungsprotokollen, zum Beispiel Routing Information Protocol (RIP) verwendet. Der Algorithmus wird verteilt, weil er mehrere Knoten (Router) innerhalb eines Autonomen Systems, einer Sammlung von IP durch einen ISP normalerweise besessenen Netzen einschließt.

Es besteht aus den folgenden Schritten:

1. Jeder Knoten berechnet die Entfernungen zwischen sich und allen anderen Knoten innerhalb ALS und versorgt diese Information als ein Tisch.
2. Jeder Knoten sendet seinen Tisch an alle benachbarten Knoten.
3. Wenn ein Knoten Entfernungstische von seinen Nachbarn erhält, berechnet er die kürzesten Wege zu allen anderen Knoten und aktualisiert seinen eigenen Tisch, um irgendwelche Änderungen zu widerspiegeln.

Die Hauptnachteile des Algorithmus von Ford des Öffentlichen Ausrufers in dieser Einstellung sind wie folgt:

• Es klettert gut nicht.
• Änderungen in der Netzwerkarchitektur werden schnell nicht widerspiegelt, da Aktualisierungen Knoten-für-Knoten ausgebreitet werden.
• Graf zur Unendlichkeit (wenn Verbindung oder Knotenmisserfolge einen von einem Satz anderer Knoten unerreichbaren Knoten machen, können jene Knoten für immer allmählich Erhöhung ihrer Schätzungen der Entfernung dazu, und inzwischen ausgeben, kann es Routenplanungsschleifen geben).

Die Verbesserung des Yens

beschrieben eine Verbesserung zum Algorithmus von Ford des Öffentlichen Ausrufers für einen Graphen ohne Zyklen des negativen Gewichts. Die Verbesserung von Yen teilt zuerst eine willkürliche geradlinige Ordnung auf allen Scheitelpunkten zu und verteilt dann den Satz aller Ränder in eine von zwei Teilmengen. Die erste Teilmenge, E, enthält alle Ränder (v, v) solch, dass ich, Ränder (v, v) solch dass i> j enthält. Jeder Scheitelpunkt wird im Auftrag v, v..., v besucht, jeden aus dem Amt scheide Rand von diesem Scheitelpunkt in E entspannend. Jeder Scheitelpunkt wird dann im Auftrag v, v..., v besucht, jeden aus dem Amt scheide Rand von diesem Scheitelpunkt in der Verbesserung von E. Yen effektiv Hälften der Zahl von "Pässen" entspannend, die für die einzelne Quelle kürzeste Pfad-Lösung erforderlich sind.

Referenzen

..

• , Die zweite Ausgabe. MIT Presse und McGraw-Hügel, 2001. Internationale Standardbuchnummer 0-262-03293-7. Abschnitt 24.1: Der Algorithmus von Ford des Öffentlichen Ausrufers, Seiten 588-592. Problem 24-1, Seiten 614-615.
• , Die dritte Ausgabe. MIT Presse, 2009. Internationale Standardbuchnummer 978-0-262-53305-8. Abschnitt 24.1: Der Algorithmus von Ford des Öffentlichen Ausrufers, Seiten 651-655.

.

Links

• C codieren Beispiel
• Open Source javanisches Graph-Paket mit Bellman-Ford Algorithms