别催了开始写啦
←第一篇
----------------------------------------------------第二篇----------------------------------------------------------
前言：
> 本文适合深色模式观看
本篇衔接第一篇《迪杰斯特拉算法精讲》
这是第二篇帖子，再不写老师就要拧我头了。
这次依旧有头图
被鲁迅医治精神的忘穿秋裤（详见鲁迅的《从百草园到三味书屋》）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
正文：
第一部分：算法讲解。
来源：百度百科
贝尔曼-福特算法（Bellman-Ford）是由理查德·贝尔曼（Richard Bellman） 和 莱斯特·福特 创立的，求解单源最短路径问题的一种算法。有时候这种算法也被称为 Moore-Bellman-Ford 算法，因为 Edward F. Moore 也为这个算法的发展做出了贡献。
你可能不认识贝尔曼，但你一定学过他与其他人发明的\color{red}你可能不认识贝尔曼，但你一定学过他与其他人发明的你可能不认识贝尔曼，但你一定学过他与其他人发明的 动态规划\huge{\color{red}动态规划}动态规划。
还记得上文的迪杰斯特拉算法吗？迪杰斯特拉算法是选边\color{red}选边选边，而贝尔曼福特算法是选点\color{red}选点选点。贝尔曼福特算法基于动态规划的思想，对图进行松弛操作。他的算法实现是：拿出所有的边，更新这个边所到达的点的最短路径。一般呢要进行 n−1n-1n−1 [1] 次松弛操作。但是，当你进行了一轮操作后没有任何一个点被更新，那么你就可以直接结束遍历。因为你已经找到了图的最短路径。时间复杂度为 O(nm)O(nm)O(nm)[1:1]。事实上下一章我们会讲到它的优化算法 SPFASPFASPFA 。但是 SPFASPFASPFA
容易被构造数据卡，所以说某些时候还是用贝尔曼福特好点。（详见ppl的评论）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
那么还是和上一篇一样，画一个图来模拟贝尔曼福特算法的实现。由于贝尔曼福特算法的实现方式，所以我画一个小一点的图。
我们定义 disdisdis 数组为图中点的最短路径，nodenodenode 结构体数组为该图的所有边。这里采用 (from,len,to)(from,len,to)(from,len,to)[2] 的形式表示，变量 ppp 代表该轮是否更新（初始为 falsefalsefalse）。下边的箭头则代表当前遍历的点。这里已经初始化好了（可以参考迪杰斯特拉算法讲解）。
先进行第一轮遍历。按照 nodenodenode 结构体开始遍历。AAA 到 DDD。计算出可得最短路径（当前，后边不再提示）为 222 ，小于无穷，更新 disdisdis 数组：
现在遍历第二条边，AAA 到 BBB。更新 BBB 点最短路径为 −2-2−2。
遍历第三条边，DDD 到 BBB。 2+3<−22+3 < -22+3<−2 ，不做更新：
为了节省时间，现在直接把第一轮遍历完：
现在还有点问题，待修改\huge{现在还有点问题，待修改}现在还有点问题，待修改
注解：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 这里设 nnn 为这个图的边数, mmm 为这个图的节点数。 ↩︎ ↩︎
2. fromfromfrom , lenlenlen 和 tototo 指从哪个点来，到哪个点去，两点之间边的权值是多少（英文看得懂吧） ↩︎
