图论--最短路--SPFA

SPFA算法(shortest path faster algorithm)算法是西南交通大学段凡丁于1994年发表的，它在Bellman-ford算法的基础上进行了改进，使其在能够处理待负权图的单元最短路径的基础上，时间复杂度大幅度降低。

算法核心：设立一个先进先出的队列用来保存待优化的节点，优化时每次取出队首节点u，并且用u点当前的最短路径估计值对离开u点所指向的节点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从从队列中取出节点进行松弛操作，直至队列空为止。

SPFA算法同样可以判断负环，如果某个点弹出队列的次数超过n-1次，则存在负环。对于存在负环的图，无法计算单源最短路径。

#include<iostream>

#include<queue>

#include<algorithm>

#include<set>

#include<cmath>

#include<vector>

#include<map>

#include<stack>

#include<bitset>

#include<cstdio>

#include<cstring>

#define Swap(a,b) a^=b^=a^=b

#define cini(n) scanf("%d",&n)

#define cinl(n) scanf("%lld",&n)

#define cinc(n) scanf("%c",&n)

#define cins(s) scanf("%s",s)

#define coui(n) printf("%d",n)

#define couc(n) printf("%c",n)

#define coul(n) printf("%lld",n)

#define speed ios_base::sync_with_stdio(0)

#define Max(a,b) a>b?a:b

#define Min(a,b) a<b?a:b

#define mem(n,x) memset(n,x,sizeof(n))

#define INF  0x3f3f3f3f

#define maxn  100010

#define Ege 100000000

#define Vertex 1005

#define esp  1e-9

#define mp(a,b) make_pair(a,b)

using namespace std;

typedef long long ll;

typedef pair<int,int> PII;

struct Node

{

    int to, lat, val; //边的右端点，边下一条边，边权

};

Node edge[1000005];

int head[1005],tot,dis[1005],N,M,vis[1005];

void add(int from, int to, int dis)

{

	edge[++tot].lat = head[from];

	edge[tot].to = to;

	edge[tot].val = dis;

	head[from] = tot;

}

void spfa(int s)

{

	memset(dis, 0x3f, sizeof(dis));

	dis[0]=0;

	memset(vis, 0, sizeof(vis));

	vis[s] = 1;

	dis[s] = 0;

	queue<int>Q;

	Q.push(s);

	while (!Q.empty()) {

		int u = Q.front();

		Q.pop();

		vis[u] = 0;

		for (int i = head[u];i;i = edge[i].lat) {

			int to = edge[i].to;

			int di = edge[i].val;

			if (dis[to]>dis[u] + di) {

				dis[to] = dis[u] + di;

				if (!vis[to]) {

					vis[to] = 1;

					Q.push(to);

				}

			}

		}

	}

}

int main()

{

    int t, x;

    scanf("%d", &t);

    while (t--)

    {

        memset(head, 0, sizeof(head));

        cini(N),cini(M);

        while (M--)

        {

            int a, b, dis;

            scanf("%d %d %d", &a, &b, &dis);

            add(a, b, dis),add(b,a,dis);

        }

        cini(x);

        spfa(x);

    }

    return 0;

}

巴特西

图论--最短路--SPFA

最新文章

热门文章