概念

SPFA（Shortest Path Faster Algorithm）和 Dijkstra算法 可谓是 单源最短路 的两大双子星了。

SPFA 由前身 Bellman-Ford-Moore（Bellman-Ford或BFM）算法添加一个队列来实现优化。
尽管如此，SPFA的复杂度最劣情况仍旧是BFM算法的复杂度，毕竟本质上只是多了一个优化的操作。

BFM算法

要知道，Richard Bellman（理查德.贝尔曼）是 动态规划 的创始人。
而BFM算法，正是运用了动态规划的思想。
相较于采用贪心思想的Dijkstra算法的无法处理 负权边，
动态规划显然没有这个限制。

松弛

那么状态是怎么转移的呢？
我们记从源点到每个节点i的距离为 dis[i]（f[i]）。（dis=distance 距离）

对于已知的当前节点i的的dis[i]，记其要转移的下一个节点j，有边权w[i][j]。（w=weight 权值）

那么显然有 dis[j] = min( dis[i]+w[i][j] , dis[j] )。

其实介个操作就叫松弛啦。

而且，当我们发现对于每个点都没法更优时，说明我们已经得到了最优解，
那么我们可以直接跳出，以优化时间。

初始化

由于我们需要的是最小值，
那么除了源点本身，其余都应该初始化为 +∞ 无穷大（INF）
而源点本身到自己的距离自然是0。

时间复杂度

显然我们需要枚举除了终点的每个 i 和 j，
故其 时间复杂度 大概为 节点数N乘以边数M，即 O（NM）。

SPFA

进行优化

我们说过了，我们可以对BFM算法加入一个队列来进行优化。

我们可以在松弛时，如果该点j可以使得当前路径更短，并且其不在队列中，再将其加入队列。

因为，如果其已在队列中，我们对其再加入队列的访问是多余的。
因为，如果后面可以继续使得路径更短，它就已经会被加入队列。

所以，我们考虑加入一个 vis[i] 来表示其是否在队列中。（vis=visited 已访问）

所以对于该点，如果有负环，显然对其的访问次数会超过N（节点数）。

那么我们可以考虑加入一个count[i]，统计每个点的访问次数，一旦超过N，说明该图存在负环。

显然，如果存在负环，那么最后最短路的结果会是负无穷。。。

于是乎，对于存在负环时，我们使函数返回 0。

模板代码

SPFA

这里大概打一下，不保证你copy过去能过。
模板还是自己打最好啦，大佬们的代码比我更好，毕竟你大佬还是你大佬。

bool SPFA(int start) 当图存在负环时，我们返回 0
{
	memset(dis,127,sizeof(dis)); 初始化dis数组为最大值
	dis[start]=0; 初始化时，源点与自身距离为 0
	memset(vis,0, ,sizeof(vis)); 初始化vis数组为 0
	vis[start]=true; 初始化时，源点入队并标记：标记
	
    queue<int> Q; 储存访问节点的队列
	Q.push(start); 初始化时，源点入队并标记：入队
	
    while(!Q.empty()) 没有可访问节点时结束
	{
        int i=Q.front();Q.pop();
        for(int j=1;j<=N;++j)
        {
            if(dis[j]>dis[i]+w[i][j]) 松弛
            {
                dis[j]=dis[i]+w[i][j];
                if(!vis[j]) 未在队列中则加入，下次访问
                {
                	vis[j]=true, 标记自身已入队
                    Q.push(j); 入队
                    if(++count[j]>N) return false; 计数，并检测负环
                }        
	        }            
        }
        vis[i]=false; 出队时，删除入队标记           
    }
    return true; 不存在负环，此时dis距离也已经处理好了
}

BFM算法

bool Bellman_Ford(int start) 同样有负环返回 0
{
    memset(dis,127,sizeof dis);
    dis[start]=0;
    int u,v,w;
    for(int i=1;i<N;++i) 对于每个点（除了终点，这里默认它为点n）
        for(int j=1;j<=M;++j) 枚举每条边，这里的edges储存每条边的出、入、权
		{
            u=edges[j].u, v=edges[j].v, w=edges[j].w;
            ij被for用了，我们用uv来代替下
            dis[v]=max(dis[v],dis[v]>dis[u]+w);
        }
    bool pd=true; 判断是否含有负权回路。
    			  如果我们最后已经理论上取得了最优解的情况下，发现还不够。
    			  说明不是我们的问题，而是有负环。
    for(int i=1;i<=M;++i)
        if(dis[edges[i].v]>dis[edges[i].u]+edges[i].w)
		{pd=false;break;}
    return pd;
}