SPFA
我们都知道一个叫SPFA的算法，它是用来计算单源最短路径的，但是，众所周知它不是很稳定，容易退化。
SPFA是基于什么被提出的？
基于一个叫做Bellman-Ford的算法。
Bellman-Ford
bellman算法实际上比dijkstra有更高的普适性，因为它可以处理有负边权图。但无法处理存在负权回路情况。
算法的时间复杂度为\(O(VE)\)，V是顶点数，E是边数。
以下是bellman-ford的伪代码：
#define MAXN 最大点数
#define MAXM 最大边数
int dis[MAXN],w[MAXM],s;//dis 表示从出发点s到i点的当前最短路径长度，w表示边权值，s表示出发点。
struct lines{//边集结构体
int u,v;//出发点，到达点
}l[MAXM];
/*
初始化，将dis[s]设为0，dis[其他]设为0x3f3f3f3f，输入边集。
*/
for(int i=1;i<=MAXN;i++){
for(int j=1;j<=MAXM;j++){
if(dis[l[j].u]+w[j]<dis[l[j].v]){
dis[l[j].v]=dis[l[j].u]+w[j];//核心代码
}
}
}
//算法结束，dis[i]就是s点到i点的最短路，若dis[i]==0x3f3f3f3f则从s点无法到达该点。
ford算法很好理解，类似动态规划。
以下是几个常见不理解的问题：
为什么distance初始化除起点外设成正无穷？
这个……肯定是为了接下来的更新啊！
对于无向图和有向图，这个算法需要变化吗？
说到点上了！对于有向图一定要记住，伪代码中的u，一定是边的入节点！相应的v，一定是出节点！
如果是无向图，我们需要做的就是反过来再执行一次。
也就是原来是这个：
if(dis[l[j].u]+w[j]<dis[l[j].v])dis[l[j].v]=dis[l[j].u]+w[j];
变成了这个：
if(dis[l[j].u]+w[j]<dis[l[j].v])dis[l[j].v]=dis[l[j].u]+w[j];
if(dis[l[j].v]+w[j]<dis[l[j].u])dis[l[j].u]=dis[l[j].v]+w[j];
为什么外层循环要用n次？
这个嘛……实际上仔细想想可以发现，运用蓝白点的思想，一开始起点S是白点，其他都是蓝点。然后由于如果还有蓝点，那么一定还有边连接着蓝点和白点。每次外层循环一定可以遍历到一些这样的边，也一定至少有一个蓝点变成白点。
这样的话，我们执行n遍外层循环，一定能保证所有点都求出了最终结果。
为什么说它不适用于负权回路？
负权回路是什么？
负权回路是指，图上一个回路，各边权值之和是负数。
相信看到这里你已经发现，如果图上存在负权回路，那么至少有两点间的最短路会是无限小！
因为可以绕这个回路走无限圈，最短路也跟着无限小……
所以：存在负权回路的图无法求出最短路。
注意是无法！目前已知算法都无法！
bellman-ford算法可以在算法结束时给出错误提示，以判断这张图是否存在负权回路：
方法：在核心代码全部结束后，执行以下代码，若仍存在某条边，使得dis[l[j].u]+w[j]<dis[l[j].v]
那么我们可以判定该图存在负权回路：
for(int i=1;i<=MAXM;i++){
if(dis[l[j].u]+w[j]<dis[l[j].v])//错误提示。
}
劣势
bellman-ford算法的缺点其实刚刚已经体现出来了！
就是，外层循环有大量重复计算！
蒟蒻过几天会写一个SPFA的讲解，SPFA其实就是ford的队列优化。
完结撒花