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: 戴克斯特拉演算法的執行時間可以因為資料結構的優化而被壓縮，待研究。
