Yens Verbesserung Bellman-Ford

Question

Ich stolperte mit berühmten Yens Optimierung Bellman-Ford-Algorithmus, die ich zunächst von Wikipedia bekam, dann fand ich die gleiche Verbesserung in mehreren Lehrbüchern im Abschnitt Übung (zum Beispiel ist dies ein Problem 24-1 in Cormen und Web exercise N5 in Sedgewicks "Algorithmen").

Hier ist die Verbesserung:

zweite Verbesserung des Yen weist zunächst einige willkürliche lineare Ordnung auf allen Ecken und dann partitioniert die Menge aller Kanten in zwei Untergruppen. Die erste Teilmenge, Ef, enthält alle Kanten (vi, vj), so dass i < j; der zweite, Eb, enthält Kanten (vi, vj), so dass i> j. Jeder Scheitelpunkt wird in der Reihenfolge v1, v2, ..., v | V | aufgesucht, wodurch jede ausgehende Kante von diesem Scheitelpunkt in Ef entspannt wird. Jeder Scheitelpunkt wird dann in der Reihenfolge v | V |, v | V | -1, ..., v1 aufgesucht, um jede ausgehende Kante von diesem Scheitelpunkt in Eb zu entspannen. Jede Iteration der Hauptschleife des Algorithmus, nach der ersten, fügt mindestens zwei Kanten zu der Menge von Kanten hinzu, deren entspannte Abstände den korrekten kürzesten Pfadabständen entsprechen: eine von Ef und eine von Eb. Diese Modifikation reduziert die Worst-Case-Anzahl von Iterationen der Hauptschleife des Algorithmus von | V | - 1 bis | V |/2.

Leider habe ich den Beweis für diese Grenze | V |/2 nicht gefunden, und außerdem scheint es, dass ich ein Gegenbeispiel gefunden habe. Ich bin mir sicher, dass ich falsch liege, aber ich kann nicht genau sehen, wo.

Das Gegenbeispiel ist nur ein Pfaddiagramm mit Scheitelpunkten von 1 bis n und Anfangsscheitelpunkt 1. (Also, E = {(i, i + 1)} für i im Bereich von 1 bis n-1). In diesem Fall ist die Menge der vorderen Ecken gleich E (E_f = E) und die Menge der hinteren Ecken ist nur die leere Menge. Jede Iteration des Algorithmus fügt nur eine korrekt berechnete Entfernung hinzu, so dass der Algorithmus in n-1-Zeit endet, was der vorgeschlagenen Grenze n/2 widerspricht.

Was mache ich falsch?

UPD: Also der Fehler war sehr dumm. Ich habe die Iteration durch Scheitelpunkte nicht berücksichtigt und über Iterationen nach sofortigen Aktualisierungen der Pfadkosten nachgedacht. Ich lösche dieses Thema nicht, weil jemand es hochgeladen hat, falls diese Verbesserung für jemanden interessant sein könnte.

Answer 1

Dies ist eigentlich der beste Fall, der in 2 Iterationen unabhängig von der Anzahl der Vertices endet.

Zeichnen Sie die Iterationen auf Papier oder schreiben Sie den Code. Die erste Iteration wird alle korrekten kürzesten Pfade finden. Die zweite Iteration wird dann nichts ändern und der Algorithmus wird beendet, weil die Menge der Scheitelpunkte, deren Entfernung sich bei der letzten Iteration geändert hat, leer ist.

Die "vorwärts" durch die Scheitelpunkte, die die Ef Menge von Kanten entspannt, wird die ganze Arbeit tun, während die "rückwärts" Ausführung nichts tun wird, weil Eb eine leere Menge ist.