spfa求最短路
给定一个n个点m条边的有向图,图中可能存在重边和自环, 边权可能为负数。
请你求出1号点到n号点的最短距离,如果无法从1号点走到n号点,则输出impossible。
数据保证不存在负权回路。
输入格式
第一行包含整数n和m。
接下来m行每行包含三个整数x,y,z,表示存在一条从点x到点y的有向边,边长为z。
输出格式
输出一个整数,表示1号点到n号点的最短距离。
如果路径不存在,则输出”impossible”。
数据范围
1≤n,m≤105,
图中涉及边长绝对值均不超过10000。
输入样例:
3 3
1 2 5
2 3 -3
1 3 4
输出样例:
2
算法的核心思路是:
对点 o、a、b、c,逐层更新邻居结点到 o的距离。
即,如果a到o的距离更新了,那么也要顺次更新c到o的距离;
如图,显然存在不止一条到a的路径,若迭代中发现某条路径(如o-b-a)更新了oa距离,
那么理应更新 oc 的距离;
c是a的后继,更新a之后,对c也是同样的处理方式。
如此往复,直到全图的数据都不再更新,计算完成。
o -...--a --- c --...
\ b /
C++ 代码
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int nMax = 1e5 + 10;
const int Inf = 0x3f, edgCnt = nMax;
// <点序号, 到源点1距离>
typedef pair<int, int> PII;
// 边的序号;
int idx = 0;
/*
wgt: 某条边的权值;
end: 某条边的终点序号;
edgeBySrc: 以某点 为起点的 边的序号;
nxtEdge:同一起点的下一条边的序号;
*/
int wgt[edgCnt], endNode[edgCnt], edgeBySrc[nMax], nxtEdge[edgCnt];
// 各点到达源点的距离;
int dst[nMax];
// 标志某结点要重新计算到达源点的距离;
bool inQueue[nMax];
int n, m;
// 为拓扑图添加一条边;
void add(int a, int b, int w) {
wgt[idx] = w;
endNode[idx] = b;
nxtEdge[idx] = edgeBySrc[a];
edgeBySrc[a] = idx++;
}
/*
spfa算法用于计算单源最短路径;
*/
int spfa() {
queue<PII> q;
// 初始化源点本身,将源点本身添加到队列中;
dst[1] = 0;
q.push({ 1, 0 });
inQueue[1] = true;
/* 处理 队列中待分析(松弛)的点,更新拓扑信息;
当待处理序列为空,则图更新完成,该图的最短距离计算结束;
若图中存在负权环,显然更新永不停止,每一圈距离都更小
—— 故不能处理负权环情况;
*/
while (q.size())
{
PII p = q.front();
q.pop();
// 处理头结点;
int srcNod = p.first;
inQueue[srcNod] = false;
// 一次性添加头结点的所有邻居,留待计算其到源点的距离;
for (int i = edgeBySrc[srcNod]; i != -1; i = nxtEdge[i]) {
// 查找到 序号为i的边 的终点结点 endNod;
int endNod = endNode[i];
// 更新其距离源点的距离;
if (dst[srcNod] + wgt[i] < dst[endNod]) {
dst[endNod] = dst[srcNod] + wgt[i];
// 尝试将其添加到待处理结点的列表中,以更新和它相关的所有结点;
if (!inQueue[endNod]) {
q.push({ endNod, dst[endNod] });
inQueue[endNod] = true;
}
}
}
}
// 若更新稳定之后,n结点 到源点的距离依然是 无穷大,无解;
if (dst[n] == 0x3f3f3f3f) return -1;
else return dst[n];
}
int main() {
cin >> n >> m;
memset(inQueue, false, sizeof(inQueue));
memset(dst, Inf, sizeof(dst));
memset(edgeBySrc, -1, sizeof(edgeBySrc));
// 逐一填充拓扑图结构;
int x, y, z;
for (int i = 0; i < m; i++) {
scanf_s("%d%d%d", &x, &y, &z);
add(x, y, z);
}
// spfa算法调用;
int ans = spfa();
if (ans == -1) printf("impossible\n");
else printf("%d\n", ans);
return 0;
}