写在前面：
Dijkstra算法是处理单源最短路径的有效算法，但它局限于边的权值非负的情况。若图中出现负权值的边，Dijkstra算法就会失效，求出的最短路径就可能是错的。
那么，我们就需要使用其他的算法来求解最短路径，Bellman-Ford算法就是其中最常用的一个。
Bellman-Ford算法非常简单，核心代码只有4行，并且可以完美地解决带有负权边的图。这里先给出其核心代码。
//【核心代码】
for(int k=1;k<=n-1;k++)
{
for(int i=1;i<=m;i++)
{
// 这里也可以写为 dis[v[i]]=min(dis[v[i]],dis[u[i]]+w[i])
if(dis[v[i]]>dis[u[i]]+w[i])
{
dis[v[i]]=dis[u[i]]+w[i];
}
}
}
Bellman-Ford：
图解流程：
到达第4轮时，我们发现，其实第4轮的操作是多余的，因为dis数组的值没有发生任何变化！是的，确实是这样的，但是，计算机并不知道呀，怎么办呢？
问题：
-
松弛操作的作用：
每一次成功的松弛操作，都意味着我们发现了一条新的最短路。 -
前k轮松弛操作的作用：
在前k轮松弛操作结束后，就已经找出了从源点发出“最多经过k条边”到达各个顶点的最短路径。 -
需要进行多少轮松弛操作：
只需要进行轮。因为在一个含有n个顶点的图中，任意两点之间的最短路径最多包含n-1条边。
-
真的最多包含n-1条边？最短路径不可能包含回路吗？
① 最多包含n-1条边，不可能包含回路。
② 最短路径肯定是一个不包含回路的简单路径。
回路分为正权回路（回路权值之和为正）和负权回路（回路权值之和为负）。
③ 如果最短路径中包含正权回路，那么去掉这个回路，一定可以得到比它更短的路径。
④ 如果最短路径中包含负权回路，那么肯定没有最短路径，因为每多走一次负权回路，就可以得到更短的路径。 -
真的一定需要n-1轮松弛操作吗？
不是的。通过上面的图我们也发现了这个问题。其实，n-1轮只是一个上界（最大值），很多时候我们会在n-1轮之前就求出了最短路径。 -
如何检测一个图是否含有负权回路？
如果经过n-1次松弛操作后，仍然可以继续成功松弛，那么，此图必定存在负权回路。
总结：
-
Bellman-Ford算法：对所有的边进行（最多）m-1次的边“松弛”操作。
-
因为最短路径上最多有n-1条边，因此Bellman-Ford算法
最多有n-1个阶段，在每一个阶段，我们对每一条边都执行松弛操作。直到进行完n-1个阶段后，便得出了最多经过n-1条边的最短路径。 -
Bellman-Ford算法流程分为三个阶段：
①初始化：初始化所有点。每一个点保存一个值，表示从原点到达这个点的距离，将原点的值设为0，其它的点的值设为无穷大（表示不可达）。
②迭代求解：进行循环，循环下标为从1到n－1（n等于图中点的个数）。在循环内部，遍历所有的边，进行松弛计算。
③检验负权回路：遍历途中所有的边（edge（u，v）），判断是否存在这样情况：dis(v) > dis(u) + w(u,v)，则返回false，表示途中存在从源点可达的权为负的回路。
之所以需要第三部分的原因，是因为，如果存在从源点可达的权为负的回路。则因为无法收敛而导致不能求出最短路径。 -
Bellman-Ford适用条件&范围：(来源：百度百科)
1.单源最短路径(从源点s到其它所有顶点v);
2.有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图);
3.边权可正可负(如有负权回路输出错误提示);
4.差分约束系统; -
时间复杂度：
，其中N为顶点数，M为边数。
参考代码：【邻接矩阵构图】
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int VexNum=1e3+1;// 顶点数
const int ArcNum=6e6;// 边数
const int INF=0x3f3f3f3f;// 正无穷
int dis[VexNum];// 距离表
int u[ArcNum],v[ArcNum],w[ArcNum];
int n,m;// n：顶点数；m：边数
bool flag;// 判断负权回路
int main()
{
scanf("%d%d",&n,&m);
//输入m条边
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&u[i],&v[i],&w[i]);
}
// 初始化距离表dis,这里以源点为 1举例
for(int i=1;i<=n;i++)
{
dis[i]=INF;
}
dis[1]=0;// 这里的源点为 1，源点也可以为其他顶点
// n-1轮(边)松弛
for(int k=1;k<=n-1;k++)
{
// 遍历每一条边
for(int i=1;i<=m;i++)
{
// 尝试对每一条边进行松弛
if(dis[v[i]]>dis[u[i]]+w[i])
{
dis[v[i]]=dis[u[i]]+w[i];
}
}
}
// 检测负权回路
flag=false;
for(int i=1;i<=m;i++)
{
if(dis[v[i]]>dis[u[i]]+w[i])flag=true;
}
if(flag)printf("此图存在负权回路\n");
else
{
for(int i=1;i<=n;i++)
{
printf("%d ",dis[i]);
}
}
return 0;
}
其实，每进行一次松弛操作，就会有一些顶点已经求得其最短路径，即这些顶点的最短路径的“估计值”变为“确定值”。此后这些顶点的最短路径的值就会一直保持不变，不再受后续松弛操作的影响。但是，每次还是会判断是否需要松弛，这里浪费了时间，可以优化吗？怎么优化？
答案是肯定的，后面我们再来介绍。
写在最后：
参考资料：
最短并非最好，有时候，学会吃亏也未尝是一件坏事。
网友评论