為什麼我們需要最多放鬆所有邊緣(V-1)
為了理解這個例子,建議對 Bellman-Ford 單源最短路徑演算法有一個簡要的想法,可以在這裡找到
在 Bellman-Ford 演算法中,為了找出最短路徑,我們需要放鬆圖形的所有邊緣。該過程最多重複 (V-1) 次,其中 V 是圖中頂點的數量。
找出從源到所有其他頂點的最短路徑所需的迭代次數取決於我們選擇放寬邊緣的順序。
我們來看一個例子:
這裡,源頂點是 1.我們將找出源和所有其他頂點之間的最短距離。我們可以清楚地看到,為了到達頂點 4 ,在最壞的情況下,它將採用 (V-1) 邊緣。現在,根據發現邊的順序,發現頂點 4 可能需要 (V-1) 次。沒得到嗎?讓我們用 Bellman-Ford 演算法找出最短的路徑: ****
我們將使用這個序列:
+--------+--------+--------+--------+
| `Serial` | 1 | 2 | 3 |
+--------+--------+--------+--------+
| Edge | 3->4 | 2->3 | 1->2 |
+--------+--------+--------+--------+
對於我們的第一次迭代:
- d [3] + 成本[3] [4] = 無窮大。它不會改變任何東西。
- d [2] + 成本[2] [3] = 無窮大。它不會改變任何東西。
- d [1] + 成本[1] [2] = 2 < d [2] 。 d [2] = 2 。父[2] = 1 。
我們可以看到我們的放鬆過程只改變了 d [2] 。我們的圖表看起來像:
第二次迭代:
- d [3] + 成本[3] [4] = 無窮大。它不會改變任何東西。
- d [2] + 成本[2] [3] = 5 < d [3] 。 d [3] = 5 。父[3] = 2。
- 它不會改變。
這次放鬆過程改變了 d [3] 。我們的圖表看起來像:
第三次迭代:
- d [3] + 成本[3] [4] = 7 < d [4] 。 d [4] = 7 。父[4] = 3 。
- 它不會改變。
- 它不會改變。
我們的第三次迭代終於找到了從 1 到 4 的最短路徑。我們的圖表看起來像: ****
因此,需要 3 次迭代才能找到最短路徑。在這之後,無論我們放鬆邊緣多少次, d []中的值都將保持不變。現在,如果我們考慮另一個序列:
+--------+--------+--------+--------+
| `Serial` | 1 | 2 | 3 |
+--------+--------+--------+--------+
| Edge | 1->2 | 2->3 | 3->4 |
+--------+--------+--------+--------+
我們得到:
- d [1] + 成本[1] [2] = 2 < d [2] 。 d [2] = 2 。
- d [2] + 成本[2] [3] = 5 < d [3] 。 d [3] = 5 。
- d [3] + 成本[3] [4] = 7 < d [4] 。 d [4] = 5 。
我們的第一次迭代找到了從源到所有其他節點的最短路徑。另一序列 1-> 2 , 3-> 4 , 2-> 3 是可能的,這會給我們後的最短路徑 2 次迭代。我們可以做出這樣的決定:無論我們如何安排序列,在這個例子中,從源頭找出最短路徑不會超過 3 次迭代。 ****
我們可以得出結論,對於最好的情況,它需要 1 次迭代才能找到來自源的最短路徑。對於最壞的情況,它將進行 (V-1) 次迭代,這就是為什麼我們重複放鬆 (V-1) 次的過程。