Aloha！我是少女人妻 Uerica！我家狗狗每天六點都會叫我起床，但除非自己很早睡，不然六點起床實在很崩潰啊，而且她看我下床就跑回去睡回籠覺(!?)，所以剛剛趁她回去睡覺時偷偷在我家客廳的瑜珈墊上假裝躺著冥想，結果沒一陣子就聽到急促的腳步聲“噠噠噠噠噠”，然後一隻狗站在我正前方，下一秒就是用腳掌巴我，巴到我坐在電腦前寫文章為止QQ

好喔大家早安，今天要繼續説說最短路徑的演算法啦～還記得昨天的達克斯特拉的演算法是不能用在負權重上嗎～所以就出現了另一個改良版，叫做貝爾曼福特演算法！

貝爾曼-福特演算法 Bellman–Ford algorithm

貝爾曼福特演算法與達克斯特拉演算法的不同處在於，貝爾曼福特演算法是用Label Correcting 的方式，簡單來說就是整個過程不斷修改路徑的權重，以找到最短路徑的方式，所以適用於有負數邊的情形，而達克斯特拉演算法則是使用 Label Setting 的方式，也就是逐一的選擇權重較小的邊來做延伸。

• 不可有長度為負數的環 (cycle)
• 從起點到所有點的最短路徑，若有 n 個點，那最短路徑則是 n-1 個邊 ，若超過 n-1 個邊，就可能有負數的環

Bellman–Ford algorithm 圖解

• 延續昨天的話題，因為疫情剛結束降至二級，有兩個地方的商家合作，開始發放現金回饋，分別是 Bank -> Store 回饋 $70 、 Castle -> Shop 回饋 $30。
  

• 跟昨天一樣，不知道到達的價格前都先設為無窮大，如果有比較便宜的價格再更新，這樣的行為稱為 Relaxation
  

• 跟昨天一樣，先從 Home 出發，出來後有兩條路，Home -> Bank 是 $150，Home -> Store 是 $50
  

• 記性不好的灰姑娘趕快先寫上她的小本本～
  

• 再從 Home 可到達的地方隨機選一個點做延伸，下圖選擇了 Bank ，Bank 可延伸出兩條路徑與計算出價格，分別是 Home -> Bank -> Bar 的 $260 ( $150 + $ 110 ) 跟 Home -> Bank -> Store 的 $80 ( $150 - $70 )
  

• 再來更新小本本～因為 Home -> Bank -> Bar 的 $260 比無窮大小，所以更新原本的資料，而剛剛的 Home -> Bank -> Store 沒有比原本的小，所以不用更新
  

• 再挑一個點做延伸，這次挑 Stroe，分別延伸出 Home -> Store -> Castle $110 ( $50 + $60 ) 、 Home -> Store -> Shop $130 ( $50 + $80 )
  

• 比對一下有沒有比較便宜，有得話就更新上去，沒有則維持不變
  

• 再選擇從 Castle 延伸的路，只有一條 Home -> Store -> Castle -> Shop 為 $80 ( $50 + $60 - $30 )
  

• Home -> Store -> Castle -> Shop 的 $80 比原本 Home -> Store -> Shop 的 $130 還便宜，所以更新上去！
  

• 最後從家裡出發到各個點最划算的路線，終於計算出來了！
  

• 剛剛前面有提到此演算法不能有負權環，是為何呢～假設今天開闢了一條免費的新道路 Castle -> Bank
  

• 而 Bank -> Store -> Castle -> Bank 這樣一趟會為賺 $10 元，所以精打細算的灰姑娘就會在這邊繞到商家都破產為止 XDD ，所以千萬不能有負權環啊～ (所謂的負數圖示是用回饋金來代表，以灰姑娘要花多少錢的角度來看，是要扣掉回饋金)
  

參考資料 :

維基百科 : 貝爾曼-福特演算法

演算法筆記 : Path

Single-Source Shortest Path：Bellman-Ford Algorithm

好啦～今天就先到這邊啦，感謝閱讀，換我來去嚕一下我家狗狗了！掰掰明天見～