最短路spfa算法的模板（加批注）

求单源最短路的SPFA算法的全称是：Shortest Path Faster Algorithm。
SPFA算法是西南交通大学段凡丁于1994年发表的。
从名字我们就可以看出，这种算法在效率上一定有过人之处。
很多时候，给定的图存在负权边，这时类似Dijkstra等算法便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了。有人称spfa算法是最短路的万能算法。

简洁起见，我们约定有向加权图G不存在负权回路，即最短路径一定存在。当然，我们可以在执行该算法前做一次拓扑排序，以判断是否存在负权回路。
我们用数组dis记录每个结点的最短路径估计值，可以用邻接矩阵或邻接表来存储图G，推荐使用邻接表。

spfa的算法思想（动态逼近法）：
设立一个先进先出的队列q用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。
松弛操作的原理是著名的定理：“三角形两边之和大于第三边”，在信息学中我们叫它三角不等式。所谓对结点i,j进行松弛，就是判定是否dis[j]>dis[i]+w[i,j]，如果该式成立则将dis[j]减小到dis[i]+w[i,j]，否则不动。
下面举一个实例来说明SFFA算法是怎样进行的：
最短路spfa算法的模板（加批注）

注：spfa大概思路有点像迪杰斯特拉算法，就是从源点开始取最近的点开始遍历并且更新距离，然而不同的是其运用的是先进先出的队列，与BFS不同，spfa算法进入队列后标记出来后又取消标记（意味着该点可能多次进出队列）。

#include <cstdio>
#include<iostream>
#include<cmath>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
vector<int>v[10005], c[10005];			//v为某点链接的对象，c为某点与链接对象的距离 //即邻接表 
const int INF = 2147483647;
int dis[10005];		//到源点的距离
bool vis[10005];		//该点是否走过
void spfa(int a)    
{
    for(int i = 0; i < 10005; ++i) dis[i] = INF;
    dis[a] = 0;
    memset(vis, 0, sizeof(vis));
    queue<int>q;q.push(a);
    while(!q.empty())
    {
        int now = q.front();q.pop();
        vis[now] = 0;    //出队后去除标记 
        for(int i = 0; i < (int)v[now].size(); ++i)		//此刻与Now这个点连接的周围的点的遍历 
        {
            if(dis[now] + c[now][i] < dis[v[now][i]])
            {
                dis[v[now][i]] = dis[now] + c[now][i];
                if(!vis[v[now][i]])
                    {q.push(v[now][i]); vis[v[now][i]] = 1;}
            }
        }
    }
}
int main()
{
    int n, m, s;
    scanf("%d%d%d", &n, &m, &s);	//n个点，m个相连情况，s为源点 
    for(int i = 0; i < m; ++i)
    {
        int f, g, w;		//输入f和g以及它们之间的之间的权值 
        scanf("%d%d%d", &f, &g, &w);
        v[f].push_back(g);c[f].push_back(w);    
    }
    spfa(s);
    for (int i = 1; i <= n; i++) printf("%d%c", dis[i], i == n ? '\n' : ' ');	//输出s点到每个点的最短距离 
}

小结：spfa算法不仅可以求最短路，也可以判断一个图中存不存在负圈。在这个算法中，一个结点可能多次入队（出队），最多入队 n 次（结点个数次），而当超过 n 次时，就证明一定存在负圈。

最短路spfa算法的模板（加批注）

相关推荐