【在厨房想30天的演算法】Day 22 演算法 : 最短路径 Shortest Path Bellman–Ford 演算法

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 ，所以千万不能有负权环啊～ (所谓的负数图示是用回馈金来代表，以灰姑娘要花多少钱的角度来看，是要扣掉回馈金)