Kann Bellman Ford Algorithmus eine beliebige Reihenfolge der Kanten haben?

Question

Ich habe gerade erst begonnen neue Algorithmen zu lernen, aber ich blieb stecken, wenn ich bellman ford Algorithmen auf Geeks für Geeks lesen: - http://www.geeksforgeeks.org/dynamic-programming-set-23-bellman-ford-algorithm/

Dort wird es geschrieben, dass-

der Algorithmus berechnen kürzesten Wege in Boden- Art und Weise. Es zuerst berechnet die kürzesten Entfernungen für die kürzesten Wege, die höchstens eine Kante im Pfad haben. Dann berechnet es die kürzesten Pfade mit höchstens 2 Kanten und so weiter.

Nach der iterten Iteration der äußeren Schleife werden die kürzesten Pfade mit höchstens i Kanten berechnet. Es kann ein Maximum | V | - 1 Kanten in jedem einfachen Pfad, deshalb läuft die äußere Schleife | v | - 1 mal. Wenn wir annehmen, dass es keinen negativen Gewichtungszyklus gibt, wenn wir kürzeste Pfade mit höchstens i Kanten berechnet haben, garantiert eine Iteration über alle Kanten, dass der kürzeste Pfad mit höchstens (i + 1) Kanten erhalten wird.

Lassen Sie uns den Algorithmus mit folgendem Beispieldiagramm verstehen. Die Bilder stammen aus dieser Quelle.

Lassen Sie den gegebenen Quellknoten 0 sein. Initialisieren Sie alle Entfernungen als unendlich, mit Ausnahme der Entfernung zur Quelle selbst. Die Gesamtzahl der Scheitelpunkte im Diagramm beträgt 5, daher müssen alle Kanten 4 Mal bearbeitet werden.

Im folgende Beispiel, wenn die Reihenfolge der Kanten zwi- (AB), (BE), (ED), (DC), (AC), (BC), (DB), (BD) dann in nur eine Iteration berechnet kürzeste Wege mit geraden Kanten, die der Behauptung widersprechen, dass "sie zuerst die kürzesten Distanzen für die kürzesten Wege berechnet, die im Pfad höchstens eine Kante haben. Dann berechnet sie kürzeste Wege mit höchstens 2 Kanten, usw. Nach der i-ten Iteration der äußeren Schleife werden die kürzesten Wege mit höchstens i Kanten berechnet "Bei der Änderung der Reihenfolge von Kanten wird sich diese Aussage als falsch erweisen.

Lassen Sie uns den Algorithmus mit folgendem Beispieldiagramm verstehen. Die Bilder stammen aus dieser Quelle.

Lassen Sie den gegebenen Quellknoten 0 sein. Initialisieren Sie alle Entfernungen als unendlich, mit Ausnahme der Entfernung zur Quelle selbst. Die Gesamtzahl der Scheitelpunkte im Diagramm beträgt 5, daher müssen alle Kanten 4 Mal bearbeitet werden.

Lassen alle Kanten in folgenden Reihenfolge verarbeitet werden: (B, E), (D, B), (B, D), (A, B), (A, C), (D , C), (B, C), (E, D). Wir erhalten folgende Abstände, wenn alle Kanten zum ersten Mal bearbeitet werden. Die erste Zeile zeigt anfängliche Abstände. Die zweite Zeile zeigt Abstände, wenn die Kanten (B, E), (D, B), (B, D) und (A, B) verarbeitet werden. Die dritte Zeile zeigt Abstände, wenn (A, C) verarbeitet wird. Die vierte Zeile zeigt, wann (D, C), (B, C) und (E, D) verarbeitet werden.

Die erste Iteration garantiert, dass alle kürzesten Pfade angegeben werden, die höchstens 1 Kante lang sind. Wir erhalten folgende Abstände, wenn alle Kanten zum zweiten Mal bearbeitet werden (die letzte Zeile zeigt die endgültigen Werte).

die zweite Iteration garantiert, dass alle kürzesten Wege zu ergeben, die höchstens 2 Kanten lang sind. Der Algorithmus verarbeitet alle Kanten 2 weitere Male. Die Abstände werden nach der zweiten Iteration minimiert, sodass die dritten und vierten Iterationen die Abstände nicht aktualisieren.

Answer 1

Die Tabellenzeile Sie sich beziehen, mit dem Kommentar

Die vierte Zeile zeigt an, wenn (D, C), (B, C) und (E, D) verarbeitet werden.

ist nicht korrekt. Es würde die Existenz eines Pfades von A zu C mit der Länge 2 bedeuten, der aus höchstens einer Kante besteht - jedoch existiert ein solcher Pfad nicht.

Answer 2

Ja, Bellman Ford funktioniert, egal in welcher Reihenfolge die Kanten bearbeitet werden. In der Tat ist dies der Grund, warum Sie n-1 Iterationen tun müssen. Wenn Sie wissen würden, was die beste Reihenfolge der Kanten ist - nur eine Iteration wäre genug.

Betrachten Sie das folgende Diagramm (alle Kanten haben Gewicht 1):

(1) --> (2) --> (3) --> (4) 

Wenn Sie die Kanten in der Reihenfolge 1->2 verarbeiten, 2->3, 3->4. Sie finden den kürzesten Weg von 1 zu 4 in nur einer Iteration. Für Kanten sortiert in Reihenfolge 3->4, 2->3, 1->2 müssen Sie alle 3 Iterationen tun.

Jedoch ist n-1 Iterationen der schlimmste Fall, egal in welcher Reihenfolge die Kanten verarbeitet werden (wenn es keine negativen Zyklen gibt).