当前位置：首页 > news >正文

SPFA算法——负权图且没有负环

news 来源：原创 2025/8/21 20:31:53

SPFA算法其实是对Bellman-ford算法的优化，Bellman-ford算法更新最短路是采用的是遍历每一条边，找到最短的边进行更新d[v]=min(d[v],d[u]+w(u,v))，由 d[v]=min(d[v],d[u]+w(u,v))可知只有当 d[ u ]变小时才有可能更新，所以用一个队列存储每次变化的点，便于更新操作

算法步骤

初始化：设源点为s，将源点s加入队列，初始化源点到自身的距离为0，即d[s]=0，其他点到源点的距离初始化为无穷大∞。

队列操作与松弛：从队列中取出一个顶点u，遍历u的所有邻接顶点v，如果d[v]>d[u]+w(u,v)（其中w(u,v)是边(u,v)的权值），则更新d[v]=d[u]+w(u,v)，且若v不在队列中，将v加入队列。

重复操作：重复步骤 2，直到队列为空。

判断负环：在执行过程中，如果某个顶点入队次数超过n−1次（n为图中顶点的个数），则说明图中存在负环，不存在从源点到其他顶点的最短路径。

例：

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。

数据保证不存在负权回路。

输入格式

第一行包含整数 n 和 m。

接下来 mm 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 impossible。

数据范围

1≤n,m≤105,
图中涉及边长绝对值均不超过 10000。

输入样例：

输出样例：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>using namespace std;typedef pair<int,int >PII;const int N = 1e6+10;
int h[N],w[N],ne[N],e[N],idx;
bool st[N];//标记点是否存在队列当中
int dist[N];
int n,m;void add(int x,int y,int z){e[idx]=y;w[idx]=z;ne[idx]=h[x];h[x]=idx++;
}void spfa(){memset(dist,0x3f,sizeof dist);dist[1]=0;queue<int> q;q.push(1);st[1]=true;//将1号点加入队列并标记为已存在while(q.size()){int t=q.front();q.pop();//每次取出队头元素并删除队头元素st[t]=false;for(int i=h[t];i!=-1;i=ne[i]){//遍历t的所有出边进行更新int j=e[i];if(dist[j]>dist[t]+w[i]){dist[j]=dist[t]+w[i];if(!st[j]){q.push(j);st[j]=true;}}}}}int main(){memset(h,-1,sizeof h);scanf("%d%d",&n,&m);while(m--){int x,y,z;scanf("%d%d%d",&x,&y,&z);add(x,y,z);}spfa();if(dist[n]==0x3f3f3f3f)printf("impossible");else printf("%d",dist[n]);return 0;
}