1.理解算法:
懒，找走最近的路
2.适用条件:
正权边(负的不适用)
3.贝尔曼-福德算法
适用条件:
适用于包含负权边的图
4.换钢琴的实例
这是交换物品的一张图，乐谱是起点（已经有的东西），现在需要花最少的钱来还到钢琴。
第一步：从起点（乐谱）出发，找到最便宜的节点。
这里只有两个节点，一个是唱片（权值为5），一个是海报（权值为0），所以选择海报这个节点。
第二步：计算前往该节点（海报）的各个邻居的开销。
父节点 节点 开销
乐谱 唱片 5
乐谱 海报 0
海报 吉他 30
海报 架子鼓 35
— 钢琴 ∞
第三步：再次执行第一步。下一个最便宜的节点为唱片。
第四部：再次执行第二步。计算前往该节点（唱片）的各个邻居的开销。
父节点 节点 开销
乐谱 唱片 5
乐谱 海报 0
唱片 吉他 20
唱片 架子鼓 25
— 钢琴 ∞
第五步：更新开销。
发现通过唱片到吉他和通过唱片到架子鼓的开销更小。所以将架子鼓和吉他的父节点更新为唱片。
第六步：重复第一步。现在起点变成了唱片。下一个最便宜的节点是吉他。
第七步：重复第二步。计算前往该节点（吉他）的各个邻居的开销。
父节点 节点 开销
乐谱 唱片 5
乐谱 海报 0
唱片 吉他 20
唱片 架子鼓 25
吉他 钢琴 40
第八步：重复第一步。起点是唱片，除了吉他，下一个最便宜的节点是架子鼓。
第九步：重复第二步。计算前往该节点（架子鼓）的各个邻居的开销。
父节点 节点 开销
乐谱 唱片 5
乐谱 海报 0
唱片 吉他 20
唱片 架子鼓 25
架子鼓 钢琴 35
第十步：更新开销。
通过架子鼓到钢琴更便宜，所以钢琴的父节点更新为架子鼓。
至此，就找到了从乐谱到各个节点的最便宜的方案，例如要还到钢琴，就需要35元。怎么确定路径呢？根据父节点向前推导就可以知道这条路径了。
