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

spfa()算法（求最短路）

news 2025/8/9 23:20:21

spfa算法是对bellman_ford算法的优化，大部分求最短路问题都可以用spaf算法来求。

注意：

（1）如若图中有负权回路，不能用spfa算法，要用bellman_ford算法；若只有负权边，则可以用

spfa算法

（2）Dijikstra算法适用于图中全都是正权边

spfa算法

step1:

初始化

step2：

取出队头结点，弹出队头，遍历队头结点的子结点，更新距离

step3：

如若第一次更新距离(st[j] == false)，将结点编号加入队列。

step4：

重复循环，直至队列没有结点编号，说明到头了。

题目如下：

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

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

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

输入格式

第一行包含整数 n 和 m。

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

输出格式

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

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

数据范围

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

解答代码如下：

//主要解决三个问题：
//（1）st数组有啥用:if(st[j] == true)//提高速度//处理重边
//（2）用spfa时，为啥图中不能有负权回路：模拟一遍就会了，因为while(q.size())
//（3）为什么要用队列？
#include<iostream>
#include<cstring>
#include<queue>using namespace std;const int N = 100010;int n,m;
int e[N],ne[N],h[N],idx,w[N];
int dist[N];
bool st[N];//如st[i]，记录的是编号i结点是否是在队列中void add(int a,int b,int c)
{e[idx] =b;w[idx] = c;ne[idx] = h[a];h[a] = idx;idx++;
}int spfa()
{memset(dist,0x3f,sizeof(dist));dist[1] = 0;queue<int > q;q.push(1);//队列q中存储的是上一次循环中被更新最短路径的结点编号st[1] = true;//st数组中存储的是此时编号 i 结点是否在队列中while(q.size()){int t = q.front();q.pop();//q中只存储上一次循环中被确定最短路径长的结点的编号，再上一次的会被弹出st[t] = false;for (int i = h[t];i != -1;i = ne[i]){int j =e[i];if (dist[j] > dist[t] + w[i])//通过if语句判定，说明编号 j 结点需要更新{dist[j] = dist[t] + w[i];if (!st[j])//判断q会不会出现重复的结点{q.push(j);//如果这个结点的距离是第一次被更新（初始值都是0x3f3f3f3f）//那么就进入队列，在下一次循环中，q队列中存储的就是上一次循环//更新路径长度的结点编号了st[j] = true;//标记编号 j 结点}}}}return dist[n];}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n >> m;memset(h,-1,sizeof(h));while(m--){int a,b,c;cin >> a >> b >> c;add(a,b,c);}int t = spfa();if (t == 0x3f3f3f3f)cout  << "impossible";elsecout << t;return 0;
}

模拟过程：

（1）为什么用队列？

spfa算法中使用队列是为了优化bellman_ford算法中的遍历每一条边来找到编号 t 结点的子结点

使用队列后，如此时t = 1，那么这一次循环中更新了 dist （第一次走到某结点时，都会更新，因为第一次走到某结点时的 dist 都是 0x3f3f3f3f ）的结点就是编号 1 结点的子结点，加更新了 dist加入到队列，下次循环时，直接取出，就可以省略遍历所有边