4–4 貝爾曼-福特演算法 Bellman-Ford Algorithm
貝爾曼-福特演算法的目的是計算圖形的最短路徑。
而最短路徑是要解決,在“加權圖形” (也就是圖形的邊有權重)中指定起點和終點,求出兩點間權重總和最小路徑的問題。
貝爾曼-福特演算法有以下幾個步驟/原則:
- 首先要設定各點的權重初始值,起點的初始值為0, 其餘各點的權重初始值為無限大∞,因為我們在一開始的時候不會知道從起點到各點有多遠,甚至是到不了。(如圖4–4–1)
2. 從起點開始任選一個連接起點到其他點的邊,開始計算並更新起點到另一點的權重。(如圖4–4–2)
3. 計算方式為:原頂點權重 + 邊的權重。計算時要以兩個方向分別進行,但可以任意從任何一個方向開始。(如圖4–4–2) (備註:以下範例為無向圖,所以兩方向都要更新,但如果是有向圖,就只要執行有指向的方向。)
4. 計算結果如果比該點權重的現值小時,權重就更新為新算出來的這個值。反之,如果比現值大,就維持現值不更新。(如圖4–4–2)
遵照原則3, 4,更新B和C的權重。
在更新完B, C之間的權重之後,發現若要從A移動到B, 走A→C→B的路徑會比走A→B還要短。
在這邊因為B的權重最後是依據邊B-C而更新,所以我們將B-C邊的顏色標為橘色,前一步驟更新的A-B邊則退回灰色。
5. 呈第四點,因為計算出的值比現況大就不需更新,也就是說,當從權重較大的點往權重較小的點計算時,只要邊的權重不為負,就可以確定不需更新。
6. 反覆對所有的頂點進行操作,有時候需要反覆進行好幾回合,才能將所有點頂權重都更新完畢。
7. 求出起點到終點的最小路徑。(如圖4–4–4)
假設圖形有n個頂點,m個邊,最多會進行n次更新的循環,而每次循環會針對每個邊進行一次檢查,所以每循環的執行時間是O(m),總執行時間為O(nm)。
4–5 戴克斯特拉演算法 Dijkstra’s Algorithm
跟貝爾曼-福特演算法一樣,戴克斯特拉演算法也是用來求出兩點間的最短路徑。
戴克斯特拉演算法有以下幾個步驟/原則:
- 跟貝爾曼-福特演算法一樣,首先要設定各點的權重初始值,起點的初始值為0, 其餘各點的權重初始值為無限大∞。(如圖4–5–1)
2. 從起點開始作為目前頂點,找出”連接目前頂點,且尚未被檢視的頂點”,作為“選項”。(如圖4–5–2)
3. 計算選項頂點的權重,計算方式為:目前頂點權重 + 邊的權重。(如圖4–5–2)
4. 跟貝爾曼-福特演算法一樣,計算結果如果比該點權重的現值小時,權重就更新為新算出來的這個值。反之,如果比現值大,就維持現值不更新。(如圖4–5–2)
5. 計算並更新所有選項頂點的權重後,從中選出權重最小的頂點,移動到該頂點,接著”加入新的選項頂點”,反覆進行上述步驟。(如圖4–5–3~圖4–5–8)
因為目前的選項C, E的權重一樣,可以從中隨機選一點作為下一個目標頂點,圖4-5-5後的例子是選C作為目標頂點。
移動到F時,因為13+7=20 小於選項G現值的14, 所以G的權重不必更新。
目前頂點已經移動到終點G,結束搜尋,橘色的線稱為“最短路徑樹”。而從起點A到終點G的最短路徑就是A→B→E→G。
戴克斯特拉演算法 vs. 貝爾曼-福特演算法
在邊的權重有負數時,戴克斯特拉演算法可能會求出錯誤的結果,例如以下情境,求A到D的最短路徑:
貝爾曼-福特演算法: 最短路徑 A→C→B→D 總權重為 4+ (-3) + 1 = 2。
戴克斯特拉演算法: 最短路徑 A→B→D 總權重為 2 + 1 = 3 ,結論錯誤。
因為當目前頂點為A, 選項為B, C時,戴克斯特拉演算法會因為B的權重較小 (2<4)而選擇B作為下一個目前頂點。
但戴克斯特拉演算法此時並不知道有C→B 這條路徑的存在,因此錯失A→C→B這條權重較小的路徑。
此外,當圖形有迴圈,且此迴圈各邊權重總和為負數時,貝爾曼-福特演算法可以藉由:”執行了n次循環但卻能持續更新頂點的權重“這件事來得到一個結論:最短路徑不存在。
但戴克斯特拉演算法無法判斷此狀況,會將錯誤的最短路徑當成正確答案,即便最短路徑根本不存在。
因此,戴克斯特拉演算法並不適合用在邊的權重有負數的情況下。但當邊的權重沒有負數時,選用執行時間較短的戴克斯特拉演算法較佳。
Note: 戴克斯特拉演算法的執行時間可以因為資料結構的優化而被壓縮,待研究。