Bellman－Ford算法
与Floyd算法一样，Dijkstra也有自己的问题，那就是无法处理“路径长度”为负的情况。（当然，城市间的距离不可能为负，但在一些特殊的问题中，路径的长度也可以为负）
为什么呢？以第一次循环为例，我们在第一次判断选择了点2为“新起点”，而没有考虑别的点经过点5达到起点1松弛的可能性。假设，点3到点2的距离为1，点3到点5的距离为-100，那点3经过点5松弛的路径实际上更短，而在Dijkstra中，却被我们忽视了。
所以，我们介绍Bellman－Ford算法来解决这种问题。（而且代码的编写也很简单，我很喜欢~~）
//Bellman－Ford算法核心部分 for(k = 1;k <= n;k++) for(i = 1;i <= m;i++) if(dis[v[i]]>dis[u[i]]+w[i]) dis[v[i]] = dis[u[i]] + w[i]; for(i = 1;i <= m;i++) if(dis[v[i]]>dis[u[i]]+w[i])
我们来讲解一下。
可以从代码中看到Bellman-ford与Dijkstra有相似的地方，都是通过松弛操作来达到最短路径。不同的是，Dijkstra是通过从近到远的顺序来按点的顺序松弛，Bellman-ford则是按输入时对每一条边的顺序来松弛。
代码中的数组u（），v（），w（）分别存储一行输入的三个数据（i点，j点，i到j的单向距离），这意味着在前文提到的邻接矩阵被我们弃用了，dist（）数组不会在这里出现了。
最外轮的k循环表示每次通过k个中转点（这里与Dijkstra相同，同样我们可以理解为经过的边的条数），i循环表示枚举m条边。
看过前面对Dijkstra的讲解，这里应该不难理解了：对每一条编号为i的边，我们比较边i的起点v[i]到起点1的距离dis[v[i]]与边i的另一点u[i]到起点1的距离+ v[i]，u[i]的间距dis[u[i]] + w[i]，更新dis（j）。（好绕。。。）那么，第k次循环就表示松弛了k次，即经过了k-1个中转点（或k-1条边）才到达起点1，留在dis（）数组中的距离就是经过中转点个数<=k-1（可能无需经过这么多个点就达到）的最短路径。（细心的朋友可以发现这句话在前文中出现过）
下面回到负值路径的问题上。因为我们是通过边为顺序松弛的，在这个过程中没有放弃对任何一条边（在Dijkstra中，我们放弃了部分数据，比如点5到点3的路径），所以不会有忽视的情况，自然也就能处理负值边了~
我们甚至还能判断负权回路（指一个回路的路径总和为负）。
等等，我们是不是还没提过为什么松弛n-1次后一定能得到最短路径？
- 1. 当没有负权回路时，对于超过n-1条边而到达起点1的路径，一定存在正值回路，肯定可以去掉；
- 2. 当有负权回路时，我们可以无限次地在回路里循环，让路径无限小，也就没有“最短路径了”。
因此，n-1次的松弛必然得到最短路径。
我们就基于2来判断负权回路。在循环n-1次后再对每一条边松弛一次，如果有还能继续松弛的边，则存在负权回路。（）
我们来看看完整版代码：
//Bellman－Ford算法解最短路径问题 #include<iostream> using namespace std; const int INF=99999; int main() { int dis[105] , i , k , n , m , u[105] , v[105] , w[105]; bool flag=false; cin>>n>>m; for(i = 1;i <= m;i++) cin>>u[i]>>v[i]>>w[i]; for(i = 1;i <= n;i++) dis[i] = INF; dis[1] = 0; //Bellman－Ford算法核心部分 for(k = 1;k <= n;k++) for(i = 1;i <= m;i++) if(dis[v[i]]>dis[u[i]]+w[i]) dis[v[i]] = dis[u[i]] + w[i]; for(i = 1;i <= m;i++) if(dis[v[i]]>dis[u[i]]+w[i]) flag=true; if (!flag) for(i = 1;i <= n;i++) cout<<dis[i]<<"\t"; else cout<<"存在负权回路！！"; }
06
SPFA算法
呼，终于来到最后一个了。。。
之前我们在谈到Bellman-ford能处理负值路径是提到，Bellman-ford没有放弃对任何一条边的松弛。这虽然不错，但也会是我们优化的一个方向。（具体的说，大神们优化的方向）
我们可以加入一个判断，判断某一条边是否被别的点帮助松弛过，因为只有被松弛过的点才能松弛别的点（被起点松弛也是松弛）。当一个点无法被松弛时，在本次经过k-1条边，它还无法接触到起点1（或者在更早的时候就已经被判断过了），也就没有帮助他人的能力。这是一个递推的过程，需要想明白。如果存在有一个点压根就没能力支援，也就是它本身已经没有存在的价值了，那么我们下次就不用再考虑它了。
注意，在这里我们依然我们始终保留了对负权路径、回路的判断。
我们可以利用队列来存放可以继续帮助松弛的点，舍弃没有利用价值的点。这和BFS是一个道理，一边要保证有k-1轮大循环来控制，一方面又要舍弃旧点增加新点，队列就可以有这个作用。所以当代码写出来是你会惊讶地发现，它和BFS的形式是那么地相似。
也不知道讲明白没，就先放代码吧。
//SPFA解最短路径问题 #include <iostream> using namespace std; int main(){ int n,m,i,j,k; int dis[105]={0},book[105]={0}; //book数组用来记录哪些顶点已经在队列中 int que[1000]={0},head=1,tail=1;//定义一个队列，并初始化队列 int dist[105][105]; int INF = 99999999; int a,b,c; cin>>n>>m; //初始化 for(i=1;i<=n;i++) dis[i]=INF; dis[1]=0; for(i=1;i<=n;i++) book[i] = 0; //初始化为0，刚开始都不在队列中 //初始化二维矩阵 for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i==j) dist[i][j]=0; //到自己的距离为0 else dist[i][j]=INF; //距离为无限，默认到不了 //读入城市之间的距离 for(i=1;i<=m;i++) { cin>>a>>b>>c; dist[a][b]=c; } //1号顶点入队 que[tail]=1; tail++; book[1]=1;//标记1号顶点已经入队 while(head<tail){//队列不为空的时候循环 for (i=1;i<=n;i++) if (dist[que[head]][i]!=INF && i!=que[head]) { k=i; // k表示每一条边的对应顶点 if(dis[k]>dist[que[head]][k]+dis[que[head]] ) //判断是否松弛成功 { dis[k]=dist[que[head]][k]+dis[que[head]]; //这的book数组用来判断顶点v[k]是否在队列中 /*如果不使用一个数组来标记的话，判断一个顶点是否在队列中每次 都 需要从队列的head到tail扫一遍，很浪费时间*/ if(book[k]==0)//0表示不在队列中，将顶点v[k]加入队列中 //下面两句为入队操作 { que[tail] = k; tail++; //同时标记顶点v[k]已经入队 book[k] =1; } } } //出队 book[que[head]] = 0; head++; } for(i=1;i<=n;i++) cout<<dis[i]<<"\t"; return 0; }
#网上很多资料提到SPFA都会提到邻接表，这里我为了偷懒就随便讲下啦~~代码中我用的是邻接矩阵存储的，请放心食用。
大致是因为，当图的边数较少时（相对于顶点而言，边数M<顶点数N^2）（我们称为稀疏图，对应稠密图），用这样的方法来存储可以极大地降低时间复杂度。
大致是利用了链表的原理实现的。有兴趣可以自己搜索。#
07
算法总结
这里直接盗用一张网络上的表来总结：
Floyd |
Dijkstra |
Bellman-ford |
SPFA |
|
空间复杂度 |
O（N²） |
O（M） |
O（M） |
O（M） |
时间复杂度 |
O（N³） |
O（（m+n）logN） |
O（MN） |
最坏也是O（NM） |
适用情况 |
稠密图和顶点关系密切 |
稠密图和顶点关系密切 |
稀疏图和边关系密切 |
稀疏图和边关系密切 |
负权 |
可以 |
不能 |
可以 |
可以 |
有负权边时 |
可以处理 不能判断 |
不能处理 不能判断 |
可以处理 可以判断 |
可以处理 可以判断 |
是不是感觉清晰些了？
那么，本期的内容到这里就全部结束了。
这里是新来的工人小舟，
正走在努力学习编程的路上。
让我们下次再见！
