别催了开始写啦
←第一篇
----------------------------------------------------第二篇----------------------------------------------------------
前言：
> 本文适合深色模式观看
本篇衔接第一篇《迪杰斯特拉算法精讲》
这是第二篇帖子，再不写老师就要拧我头了。
这次依旧有头图
被鲁迅医治精神的忘穿秋裤（详见鲁迅的《从百草园到三味书屋》）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
正文：
第一部分：算法讲解。
来源：百度百科
贝尔曼-福特算法（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的评论）
看什么看\HUGE{看什么看}看什么看
注解：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 这里设 nnn 为这个图的边数, mmm 为这个图的节点数。 ↩︎ ↩︎
