这种算法用于寻找单源最短路以及判断负环.
Bellman-Ford算法的核心思想就是：
一个有n个点的图中的任意一条没有负环的最短路径最多只有n-1条边.
简单点说就是最短路径是一条简单路径.
好像是这样的（就是这样的）.
那么既然是单源的最短路，那么我们就可以用每条边不断地迭代更新.
最多更新n-1次，假设更新了超过n-1次，即可判断有负环.
那我们就可以这样设计一个算法：
1.将源点到源点的距离d[start]赋值为0，其余赋值为无穷大.
2.枚举所有的边，进行三角形迭代.
3.假设没有继续更新，停止跟新.
4.如此执行下去，假若执行了n次，说明有负环.
bool bellman_ford(int start){
memset(dis,10,sizeof(dis));
dis[start]=0;
bool b;
for (int i=1;i<=n;i++){
b=0; //标记清零
for (int j=1;j<=m;j++) //枚举每一条边
if (dis[e[j].x]+e[j].v<dis[e[j].y])
dis[e[j].y]=dis[e[j].x]+e[j].v,b=1; //三角形迭代
if (!b) return false; //如果没有更新，返回假，即没有负环
}
return true; //更新n次，说明有负环
}
Bellman-Ford可简单了，时间复杂度为O(nm).
当然，我们可以将源点更新为0也看做一次更新.
我们可以确定，只要会更新的，之前肯定会有一个跟它连接的点更新.
为什么？我们可以想一想，假设没有更新与它相连的点，那么三角形迭代会更新它吗？
于是我们可以考虑优化策略.
我们可以将所有更新过的点放入一个队列，让后将这个队列里的所有点进行更新.
而且如果队列里已经有了这个数，我们也不用再次把这个点加入队列了.
为什么？因为这个点还是会更新的.
这就是spfa算法.
代码如下：
const int maxn=1000010;
class qu{
int q[maxn];
bool v[maxn];
int h,t;
void clear() const{
h=0;t=-1;
for (int i=0;i<maxn;i++)
v[i]=false;
}
void push(int x) const{
if (!v[x]) q[++t]=x;
}
void pop() const{
++h;
}
int top() const{
return q[h];
}
bool empty() const{
return (h>t) true:false;
}
}; //手打队列没毛病
bool bellman_ford(int start){
memset(dis,10,sizeof(dis));
dis[start]=0;
qu.push(start);
while (!qu.empty()){
for (int i=lin[qu.top()];i;i=e[i].next)
if (dis[e[i].x]>dis[qu.top()]+e[i].v){
dis[e[i].x]=dis[qu.top()]+e[i].v; //三角形迭代
qu.push(e[i].x); //迭代成功，将这个点入队用于更新
}
}
}
当然，这个队列也可以换成栈.
V为入队次数的话，
时间复杂度为O(V).
假设没有负环，最坏时间复杂度为O(nm).
但一般不会卡你的spfa（因为数据出不出来）.
那么如何判负环呢？
只需多加一个数组，记录每个点入队了几次，如果入队了n次，说明有负环.