Bellman-Ford演算法

習題預習

1. 給定一個加權有向圖，請使用Bellman-Ford Algorithm找出起點到所有其他頂點的最短路徑。

2. 給定一個加權有向圖和兩個頂點，請使用Bellman-Ford Algorithm找出這兩個頂點之間的最短路徑。

3. 給定一個加權有向圖和起點，請使用Bellman-Ford Algorithm判斷是否存在負環。

4. 給定一個加權無向圖和起點，請使用Bellman-Ford Algorithm找出起點到所有其他頂點的最短路徑。

5. 給定一個加權有向圖，其中某些邊權重為負數，請使用Bellman-Ford Algorithm找出最長路徑。

說明知識

Bellman-Ford Algorithm是用來解決單源最短路問題的一種算法，可以處理存在負權邊的圖。該算法基於對每一條邊進行V-1次松弛操作(其中V是圖中的節點數)，來得到從源點到所有節點的最短路程。

演算法過程中，提供了一個最短路程表，存儲所有節點到源點的最小路程。該表一開始會被初始化為至少為無限大。 Bellman-Ford Algorithm 重複進行V-1次的下列迴圈：

1. 對圖中的每一條邊，對其端點進行松弛操作(如果端點的最短路程可以被更新，就更新最短路程表中的路徑長度)。

例如，考慮下面的圖表示法，它有5個節點。

假設起點是節點1。一開始初始化最短路程表為無限大， SOURCE = (0), OTHERS = (+∞)。

對每條邊(Tx, Ty, c)進行V-1=4次的松弛操作，一直將節點3、4、5的最短路維護到最新值。

第1次：

T1 = 0;
T2 = +∞;
T3 = +∞;
T4 = +∞;
T5 = +∞;

SOURCE = (0), OTHERS = (T1 T2 T3 T4 T5)

...

T3 = min(T3, T1 + 6) = 6;
T2 = min(T2, T1 + 3) = 3;

SOURCE = (0), OTHERS = (T1 3 6 T4 T5)

第2次：

T1 = 0;
T2 = 3;
T3 = 6;
T4 = +∞;
T5 = +∞;

SOURCE = (0), OTHERS = (T1 T2 T3 T4 T5)

...

T4 = min(T4, T2 + (-1)) = 2;
T5 = min(T5, T3 + 1) = 7;

SOURCE = (0), OTHERS = (T1 3 6 2 7)

第3次：

T1 = 0;
T2 = 3;
T3 = 6;
T4 = 2;
T5 = 7;

SOURCE = (0), OTHERS = (T1 T2 T3 T4 T5)

...

T5 = min(T5, T4 + 3) = 5;

SOURCE = (0), OTHERS = (T1 3 6 2 5)

第4次：

T1 = 0;
T2 = 3;
T3 = 6;
T4 = 2;
T5 = 5;

SOURCE = (0), OTHERS = (T1 T2 T3 T4 T5)

...

Done!

彙總重點

• Bellman-Ford Algorithm是一种用于在加权有向图中找到单源最短路径的算法。
• 在算法的开始，所有的节点的距离值被初始化为无穷大，除了起点节点，其距离值为零。
• 然后，算法开始通过边的松弛来逐步减小节点的距离值。
• 在每次迭代中，算法遍历所有的边，并尝试对它们进行松弛操作。如果在这个过程中发现了一条更短的路径，那么节点的距离值将被更新为更短的值。
• 在算法执行的过程中，如果发现某些节点的距离值一直在被修改，那么这可能是存在负权重环的信号。
• 最终，算法会给出起点到所有其他节点的最短路径和距离值。如果存在负权重环，则算法会停止，并提示该图不适合使用Bellman-Ford Algorithm进行处理。
• 该算法具有较高的时间复杂度，为O(VE)，其中V表示节点数目，E为边数。

知識測驗

1. 給定一個帶有權重的有向圖，求從給定源點出發到達所有其他節點的最短路徑，如果圖中存在負權環，輸出不存在解決方案。

答案: 該問題可以使用貝爾曼福德算法解決。詳細解答請見貝爾曼福德算法的相關資料。

2. 給定一個帶有權重的有向圖，求是否存在一條負權環。

答案: 同樣可以使用貝爾曼福德算法解決。從每一個節點出發進行遍歷，當走到一個節點時發現它的最短路徑不斷被更新，這意味著這個圖中存在一個負權環。

3. 給定一個帶有權重的無向圖，求任意兩點之間的最短路徑。

答案: 該問題可以使用Dijkstra算法或貝爾曼福德算法解決。但是，貝爾曼福德算法可以處理負權環，而Dijkstra算法無法處理。

4. 給定一個帶有權重的有向圖，求從給定點到達所有其他節點的最短路徑，但是某些邊是雙向而且權重相同。

答案: 該問題可以使用貝爾曼福德算法解決，因為算法無需考慮邊的方向，而僅僅是要通過存在的邊遍歷所有節點。

5. 給定一個帶有權重的有向圖，求給定節點到達其他節點的最短路徑，但是有一些節點被限制，無法到達。

答案: 該問題可以使用貝爾曼福德算法解決，但是需要進行一些額外的處理。首先，我們希望在進行運算時不考慮這些不可到達的節點，在算法運行之前，我們需要將這些節點的所有入邊都移除。這樣，算法就不會考慮那些無法到達的節點，可以正確地計算出其他節點的最短路徑。