福特-贝尔曼算法
让我们得到一个有向加权图 G，它有 n 个顶点和 m 个边，以及一些起始顶点 v 。需要找到从顶点 v 到所有其他顶点的最短路径的长度。
与 Dijkstra 一样， Ford-Bellman 寻找从顶点 1 到所有其他顶点的距离，但使用负边缘 /强>.
<分区>
Ford-Bellman 算法本身由几个阶段组成 (
n-1)。在每个阶段，都会检查图的所有边，算法会尝试沿着成本
c 的每条边
(a, b) 放松。
沿边缘松弛 ——这是对
d[a]意义的改进 值
d[b] + c。事实上，这意味着我们正在尝试通过使用边缘来改进顶点的答案 以及顶部的当前答案。
d数组是距离起始顶点最短长度的数组，就像在Dijkstra中一样，我们一开始用尽可能大的数字填充它，除了起始顶点，你需要在其中放入0.
存储边时，不是使用邻接矩阵或权重矩阵，而是一个列表，表示边从哪个节点离开（
from），到达（
to） code>) 及其重量 (
cost)。
结构边{
int 从，到，成本；
};
矢量<边>边缘；
INF 常量表示数字“无穷大” - 必须以明显超过所有可能路径长度的方式进行选择。
最简单的算法实现：
d[v] = 0;
for (int i=0; i
或使用语法
C++11 缩短一点：
d[v] = 0;
for (int i=0; i< n-1; ++i)
for (edge j: 边)
如果（d[j.from]
工作实例
拿一个简单的有向图 有 5 个节点，4 条边，权重等于 1。
让我们按顺序介绍一个边列表。
4 5 1
3 4 1
2 3 1
1 2 1
最短长度数组的初始值：
<正文>
| 0 |
信息 |
信息 |
信息 |
信息 |
其中 inf 应该是一个匹配的整数，它总是大于边的权重。
第一关后
<正文>
| 0 |
1 |
信息 |
信息 |
信息 |
第二关之后
<正文>
| 0 |
1 |
2 |
信息 |
信息 |
第三关之后
<正文>
| 0 |
1 |
2 |
3 |
信息 |
第四关之后
<正文>
| 0 |
1 |
2 |
3 |
4 |
如果我们按从 1 到最后的顺序馈送边，我们可以在第 1 遍之后找到最短的长度。