「spfa」最短路 SPFA 算法详解与模板

spfa

转载请注明出处HTTPs://blog.csdn.net/bestsort

个人感觉看SPFA之前推荐先看最短路 dijkstra 算法详解与模板

因为只有脑中理解了Dijkstra的寻路过程，相互印证下，才能更好的理解SPFA

SPFA核心思想：如果一个点上次没有被松弛过，那么下次就不会从这个点开始松弛。每次把被松弛过的点加入到队列中，就可以忽略掉没有被松弛过的点

而且SPFA相比dijkstra算法还有个优势：可以处理负权图和判负环，判负环只需要再加一个if和统计入队次数的num数组即可（注释部分）

每一行代码的含义都在代码注释里了

附一道例题:HDU2544

最短路

Time limit: 5000/1000 MS (java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 83934 Accepted Submission(s): 36317

Problem Description

在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？

Input

输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。

输入保证至少存在1条商店到赛场的路线。

Output

对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间

Sample Input

2 11 2 33 31 2 52 3 53 1 20 0

Sample Output

#include <iOStream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#define For(a,b) for(int a=0;a<b;a++)
#define mem(a,b) memset(a,b,sizeof a)
using namespace std;
typedef long long ll;
const int maxn =  1e3+5;
const int INF = 0x3f3f3f3f;     //无穷大
const int inf = 0x3f;
const double PI = acos(-1);
struct edge {
    int e,w;
    edge(int _e,int _w) {       //构造函数,使用edge(a,b) 可以直接构造一个e = a,w = b结构体
        e = _e,w = _w;
    }
    //如果需要申请结构体变量,还需要加上下面这个构造函数
    //edge(){};(对没错里面都是空的)
};
vector<edge> Map[maxn];         //邻接表存图
bool vis[maxn];                 //该点是否在队列中
int dis[maxn];                  //初始点到每点的最短距离
int n,m;
void spfa(int a) {
    memset(dis,inf,(n+1)<<2);   //将数组中前n+1个数初始化为无穷大
    mem(vis,0);
    dis[a] = 0;
    vis[a] = true;
/*****************上面都是和Dijkstra一样的，接下来才是重头******************/
/**Dijkstra：每次找权值最小的边，然后根据这个边所连的点更新dis数组
所以每n次操作只能找出一个点来
   SPFA：如果该边可以松弛且连接的点未被使用，就把该边连接的那个点存进队列等待更新
   所以每经过一个点就可以把该点所有边所连接的点（可以被松弛的）都记录然后更新
*/
    queue<int>q;
    q.push(a);
    while(!q.empty()) {
        int buf = q.front();                //取出队首的点
        q.pop();
        vis[buf] = 0;

        For(i,Map[buf].size()) {
            int p = Map[buf][i].e;          //取出队首的点
            int w = Map[buf][i].w;
            if(dis[buf]+w < dis[p]) {       //如果可以松弛就更新dis数组，此处和Dijkstra一样
                dis[p] = dis[buf]+w;        //松弛的同时如果该点未被访问就把该点扔进队列
                if(!vis[p]) {               //不同的地方，如果p点未被使用，则将其放入队列（也就是p点可以被松弛）
                    //num[p]++;
                    //if(num[p]>n+1)
                        //return false;
                    q.push(p);
                    vis[p] = 1;
                }
            }
        }
    }
    //return true;
}


int main() {
    int p1,p2,w;
    while(cin >> n >> m) {
        if(!n&&!m)
            break;
        For(i,n)
        Map[i].clear();
        For(i,m) {
            cin >> p1 >> p2 >> w;
            //构建无向图
            Map[p1].push_back(edge(p2,w));
            Map[p2].push_back(edge(p1,w));
        }
        spfa(1);
        cout << dis[n] <<endl;
    }
    return 0;
}

最短路 SPFA 算法详解与模板

spfa

最短路

相关阅读

栏目导航

推荐阅读

热门阅读