日元對貝爾曼福特的改進

Question

我偶然發現了着名日元優化的貝爾曼福特算法，我最初從Wikipedia開始，然後在練習部分的幾本教科書中找到了相同的改進（例如，這是一個問題24-1在科爾曼和Web exercise N5 Sedgewick的「算法」）。

這裏的改進：

日元的第二個改進第一分配上所有頂點一些任意線性順序，然後分隔所述集合中的所有邊緣的成兩個子集。第一個子集Ef包含所有的邊（vi，vj），這樣我就可以：第二個Eb包含邊（vi，vj），使得i> j。按照v1，v2，...，v | V |的順序訪問每個頂點，放鬆Ef中該頂點的每個輸出邊。然後以v | V |，v | V | -1，...，v1的順序訪問每個頂點，放寬Eb中該頂點的每個輸出邊。算法主循環的每次迭代在第一次迭代之後，將至少兩條邊添加到鬆弛距離與正確最短路徑距離相匹配的一組邊緣：一個來自Ef，一個來自Eb。此修改將算法主循環的最壞情況迭代次數從| V |中減少 - 1到| V |/2。

不幸的是，我沒有設法找到這個bound | V |/2的證明，而且，似乎我找到了一個反例。我確信我錯了，但我看不清楚究竟在哪裏。

反例只是一個頂點標記從1到n和初始頂點1的路徑圖。（因此，對於範圍從1到n-1的i，E = {（i，i + 1）}。在這種情況下，前向頂點集合等於E（E_f = E），而向後頂點集合僅僅是空集合。算法的每次迭代只增加一個正確計算的距離，所以算法在n-1時間內完成，這與提出的邊界n/2相矛盾。

我在做什麼錯？

UPD：所以這個錯誤是非常愚蠢的。我沒有考慮通過頂點的迭代，思考迭代以及路徑成本的即時更新。我並沒有刪除這個話題，因爲有人贊成這個話題，以防這種改進對某人有意思。

Answer 1

這實際上是在2次迭代中完成的最佳情況，無論頂點的數量如何。

在紙上繪製迭代或編寫代碼。第一次迭代將找到所有正確的最短路徑。第二次迭代不會改變任何東西，並且算法終止，因爲上一次迭代改變距離的頂點集合是空的。

「前進」運行通過放寬Ef邊緣集的頂點將完成所有工作，而「向後」運行將不會執行任何操作，因爲Eb是空集。