Bellman-Ford-Algorithmus - Warum können Kanten nicht in der richtigen Reihenfolge aktualisiert werden?

Der Bellman-Ford - Algorithmus bestimmt den kürzesten Weg von einer Quelle zu allen anderen Ecken. Anfangs ist der Abstand zwischen und allen anderen Scheitelpunkten auf . Dann wird der kürzeste Weg von zu jedem Scheitelpunkt berechnet; das geht weiter für Iterationen. Meine Fragen sind: $s$ $s$ $\infty$ $s$ $|V|-1$

Warum muss es Iterationen? $|V|-1$
Würde es etwas ausmachen, wenn ich die Kanten in einer anderen Reihenfolge überprüfe?
Angenommen, ich überprüfe zuerst die Kanten 1, 2, 3 und dann bei der zweiten Iteration die Kanten 2, 3, 1.

MIT Prof. Eric sagte, dass die Reihenfolge keine Rolle spielt, aber das verwirrt mich: Würde der Algorithmus einen Knoten, der auf Kante basiert, nicht fälschlicherweise aktualisieren, wenn sein Wert von Kante abhängt, aber nach aktualisiert wird ? $x_2$ $x_1$ $x_1$ $x_2$

algorithms shortest-path user1675999
quelle

Welche Implementierung sehen Sie? Bei der dynamischen Programmierung hat man natürlich kein Problem mit der Reihenfolge; für andere mag es nicht trivial sein.

Raphael

Antworten:

Betrachten Sie den kürzesten Weg von nach , $s$ $t$ . Dieser Pfad besteht aus höchstens Kanten, da das Wiederholen eines Scheitelpunkts auf einem kürzesten Pfad immer eine schlechte Idee ist (oder zumindest gibt es einen kürzesten Pfad, der keine Scheitelpunkte wiederholt), wenn wir keine negativen Gewichtszyklen haben. $s, v_1, v_2, \dots, v_k, t$ $|V|-1$

In Runde 1 wissen wir, dass die Kante gelockert wird, sodass die Entfernungsschätzung für nach dieser Runde korrekt ist. Beachten Sie, dass wir zu diesem Zeitpunkt keine Ahnung haben, was ist, aber da wir alle Kanten entspannt haben, müssen wir auch diese entspannt haben. In Runde zwei entspannen wir uns $(s, v_1)$ $v_1$ $v_1$ . Wir haben noch keine Ahnung, was oder sind, aber wir wissen, dass ihre Entfernungsschätzungen korrekt sind. $(v_1, v_2)$ $v_1$ $v_2$

Wiederholen Sie dies nach einer Runde wir , so haben wir uns entspannt , wonach die Entfernungsschätzung für korrekt ist. Wir haben keine Ahnung, was ist, bis der gesamte Algorithmus beendet ist, aber wir wissen, dass es irgendwann passieren wird (vorausgesetzt, es gibt keine negativen Gewichtszyklen). $k+1$ $(v_k, t)$ $t$ $k$

Die entscheidende Beobachtung ist also, dass nach Runde die Entfernungsschätzung des ten Knotens des kürzesten Pfades auf den richtigen Wert gesetzt werden muss. Da der Weg höchstens ist Kanten lang, Runden reichen aus, um diesen kürzesten Weg zu finden. Wenn ein Die Runde ändert noch etwas, dann passiert etwas Seltsames: Alle Pfade sollten bereits auf ihre endgültigen Werte "festgelegt" sein, also müssen wir die Situation haben, dass ein negativer Gewichtszyklus existiert. $i$ $i$ $|V|-1$ $|V|-1$ $|V|$

Alex ten Brink
quelle

Ich habe hier einen kleinen Zweifel. Ich glaube, dass | v | -1 die ungünstigste Anzahl von Runden ist, nach der der kürzeste Weg von s nach t berechnet wird Kanten werden in dieser Reihenfolge ausgewählt, sagen wir (s, v1), (v1, v2). (vn, t), dann haben wir in einer einzelnen Iteration selbst den kürzesten Weg von s nach t. Dies ist nur zum Verständnis und in In der Praxis wissen wir nicht, in welcher Reihenfolge Kanten ausgewählt werden und daher | v | -1 Runden. Habe ich recht?

Whokares

@whokares: ja, du könntest Glück haben und den kürzesten Weg in der ersten Runde finden. Sie wissen bis zur letzten Runde nicht genau, dass der Wert, den Sie finden, der kürzeste Weg ist, aber es könnte sein, dass dies der Fall ist. Der Dijkstra-Algorithmus bewirkt im Wesentlichen Folgendes: Wenn alle Kanten nicht negative Gewichte aufweisen, "sagt" die Prioritätswarteschlange, die im Dijkstra-Algorithmus verwendet wird, die Reihenfolge voraus, in der Sie Kanten entspannen sollten, damit Sie in Ihrer ersten Runde der Relaxationen alle kürzesten Pfade finden.

Alex ten Brink

Vielen Dank für das Update. Ich habe es bekommen. In einem der Materialien wird es als <br> Folie 6 erwähnt: Eine schlechte Wahl der Relaxationsreihenfolge kann zu exponentiell vielen Relaxationen führen: <br> Folie 8: „Intelligente“ Reihenfolge der Kantenrelaxationen <br>

whokares

Unabhängig von der Reihenfolge der Kanten in jeder Iteration werden die kürzesten Pfade in | v | -1 Iterationen berechnet, richtig? Warum sagt er exponentiell. Bedeutet er, dass, wenn wir für alle Iterationen, die wir normalerweise ausführen, dieselbe Reihenfolge wählen, der Relaxationscode aufgerufen wird, die Aktualisierung der Bezeichnung für einen Scheitelpunkt jedoch aufgrund der Reihenfolge möglicherweise nur seltener erfolgt, wodurch der Prozessor gespart wird Zeit?

Whokares

@whokares: Der erste Algorithmus, den sie präsentieren (der eine exponentielle Laufzeit haben kann), lockert nicht alle Kanten in einer Runde, sondern findet eine Kante, für die eine Relaxationsoperation etwas ändern würde, und lockert diese Kante. Wenn Sie so weitermachen und es keinen negativen Gewichtszyklus gibt, helfen Ihnen eventuell keine Kanten mehr und Sie hören auf. Da Sie jedoch keine Runden und keine festgelegte Reihenfolge haben, an der Sie sich als Nächstes entspannen müssen, werden Sie möglicherweise eine exponentielle Anzahl von Relaxationen durchführen. Der verbesserte Algorithmus, den sie präsentieren, ist Bellman-Ford, der Runden hat.

Alex ten Brink

Der längste Weg ohne Zyklen ist |V|. Wir beginnen mit einer Quelle, also haben wir bereits einen Pfad der Länge 1, also brauchen wir |V| - 1mehr Knoten, um den längsten Pfad zu erhalten.

Die Reihenfolge spielt keine Rolle, da bei jeder Reihenfolge die Invariante beibehalten wird: Nach nIterationen ist der Wert für jeden Knoten kleiner oder gleich den Kosten des minimalen Kostenpfads von szu dem Knoten, der höchstens nKanten enthält.

Wenn zu Beginn einer Iteration die Kosten bis zu den nKnoten korrekt sind, sind sie am Ende der Iteration bis zu den n+1Knoten korrekt . Eine Neuordnung kann dazu führen, dass einige Knoten niedrigere Kosten verursachen, bevor sie normalerweise aktualisiert werden, aber sie werden schließlich trotzdem aktualisiert.

fgb
quelle

Ich weiß nicht, ob es nur ich ist, oder ich kann mir diese Fakten nicht so leicht vorstellen. Ich denke immer noch, dass es einige Knoten gibt, die in den V-1-Iterationen nicht aktualisiert wurden.

user1675999

Nein, Sie haben | E | = | V | -1 Kanten, wenn Sie | V | haben Knoten, die durch einen einfachen Pfad ohne Zyklen verbunden sind. Und Sie haben | V | -1 Iterationen, löschen Sie Ihre Antwort, weil es falsch ist.

Sam

@sam Wer bist du und was haben deine Aussagen mit der Antwort zu tun?

fgb