bellman-ford

基本思想：

该算法以自下而上的方式计算出最短路径。

首先计算路径中最多有一条边的最短距离。

然后，计算最多有 2 条边的最短路径，依此类推。在外循环的第 i 次迭代之后，计算最多具有 i 条边的最短路径。可以有最大值 |V| – 任何简单路径中的 1 条边，这就是外循环运行 |v| 的原因 – 1 次。这个想法是，假设如果我们计算了最多具有 i 个边的最短路径，则没有负权重循环，那么对所有边的迭代保证给出最多具有 (i+1) 个边的最短路径。

算法步骤 ：

1、初始化 dis 数组为正无穷， dist[1] = 0

2、（外层循环）循环 i 从 1 到 n ，遍历 n 次表示：是不经过超过 i 条边到达终点的最短距离

1. （内层循环）循环 i 从 1 到 m， 遍历 m 条边，把所有的边都进行松弛操作

如图描述的是在有5个结点的图上运行bellman-ford算法的过程。

SPFA

算法思想：

队列优化，去掉一些无用的松弛操作，用队列来维护松弛造作的点。继承了Bellman-Ford算法的思想，但时间复杂度相对来说提高了很多。

与BFS的算法有一些类似，利用了STL队列。

实质是广度优先遍历。

算法步骤：

1 创建一个队列q，源点 u 入队，标记 u 在队列中，u 的入队次数加1。

2 松弛操作。取出队头节点 x，标记 x 不在队列中。扫描所有 x 的所有出边 i(x,c,w),如果 dis[c]>dis[x]+e[i].w,令 dis[c]=dis[x]+e[i].w。如果节点 v 不在队列中，判断 c 的入队此时加1后大于或等于 n，则说明有负环，退出；否则 c 入队，标记 c 在队列中。

3 重复松弛操作，直到队列为空。