哈囉大家好
今天我要來教大家：貝爾曼-福特演算法
和它與戴克斯特拉演算法的差別
我很快將會放上另一支影片
關於貝爾曼-福特演算法的運行
會有一步一步的範例介紹
如果你還沒看過我戴克斯特拉演算法的影片
請你花個幾分鐘先看過
首先
貝爾曼-福特演算法和戴克斯特拉演算法有一樣的結果
那就是他們都會得出圖裡
從一個點到剩下全部點的最短路徑
這邊提醒一下
普林演算法和克魯斯克爾演算法
會導出“最小生成樹”
這兩個演算法醉到的不同就是
貝爾曼-福特演算法可在負權值得邊上運行
但戴克斯特拉演算法不行
不過
但兩者皆會卡在負迴圈
因為在這種情況下
最短路徑並不存在
在負迴圈
一直在裡面跑
然後“路徑”就會一直變小
為什麼戴克斯特拉演算法會在有負權值邊時卡住
原因是因為
戴克斯特拉演算法是“貪婪演算法”
但貝爾曼-福特演算法不是
這邊我們給個例子
在接下來這個圖中
戴克斯特拉可以正確的算出
從s到a的最短路徑是3
那如果我們把2換成複數呢
在第一次迭代中
戴克斯特拉仍會挑選a然後刪除它
所以到a的路再也不會被更新
但我們當然知道
現在到a的最短路徑
是走經過B的-2那條邊
這就是用上貝爾曼的地方了
我將會用下圖來解釋
貝爾曼背後的理論
假如要求S到D的最短路徑
該怎麼做呢
嗯...
我們迭代四次
每次都把權值加到路徑清單裡
為什麼要迭代四次
並且為什麼這很重要
這是貝爾曼背後的基礎想法
從原點到任一其他點的路上
可有至少B-1條邊
這是為什麼
如果有人跟你說
從S到D的路上
有五或更多條邊
那將會需要一個
已經在路徑上的點到點的新路
也就是“迴圈”
既然我們知道這不能有路迴圈
我們可以拿掉這條邊
來減少距離
再一次的
v條或更多的邊在路徑中
代表有重複（走到）的點
並且導致成為一個迴圈
所有路徑都要變簡潔（沒有迴圈）
回到我們的範例
已知從V-1次迭代
保證可以找到S到D的最短路徑
我們在每個迭代時要做什麼呢
因為貝爾曼不是貪心法
我們將在迭代時
更新”每個“邊
更新意味著
檢查每個邊
且確認他是否減少最短路徑距離
這也許有些讓人困惑
所以看一下這個虛擬碼
如果你仍然抱有疑問
請繼續觀看我下支影片
我會確實教你貝爾曼如何在圖上執行
我這支影片的用意
是教你貝爾曼的理論
和它與戴克斯特拉演算法的差異
時間複雜度是O(|V|*|B|)
B是點的個數
E是邊的個數
你可以輕易的從虛擬碼推出這個
謝謝你的觀看
如果你有任何問題
你可以在下面留言
然後我會盡力回答你
如果你喜歡這支影片
你可以考慮幫我按讚和追蹤
如果你有想要我講的主題
請在下方回應
感謝
