本文主要是介绍【算法】spfa算法求最短路（没有负环），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。
数据保证不存在负权回路。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 impossible。
数据范围
1 ≤ n,m ≤ 1e5
图中涉及边长绝对值均不超过 10000。
思路
bfs思想，将节点1的距离初始化为0，存入队列中进入循环。在循环中从队列中取出一个节点p，使用节点p对p的后继节点a进行更新（如果1->...->a的距离大于1->...->p->a的距离，则对a节点进行更新，如果点a不在队列中，就把点a放入这个队列中），将p的后继节点遍历完之后进入下一次循环，直到队列为空（如果存在负环，则会进入无限循环，但是题目保证不存在负环）。
代码
#include<bits/stdc++.h>
#define int long long
#define N 100100
using namespace std;int n,m;// n表示点数，m表示边数
int w[N],e[N],ne[N],h[N],idx;// 邻接表四件套，w数组储存点a到点b的距离
int dist[N];// dist数组储存点1到点i的距离
bool st[N];// 用来记录点i是否在队列q中
queue<int> q;// bfs核心
void add(int a,int b,int c)
{w[idx] = c,e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}void spfa()
{memset(dist,0x3f,sizeof(dist));//将距离初始化为无穷大dist[1] = 0;// 点1到点1的距离为0st[1] = true;// 将点1储存到队列中q.push(1);while(!q.empty()){int t = q.front();q.pop();//将节点从队列中取出st[t] = false;// 标记一下点t已经不在队列中了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])// 如果这个点满足dist[j] > dist[t] + w[i]的条件，并且不再队列内部，则将其放入队列中{q.push(j);st[j] = true;}}}}
}int32_t main()
{memset(h,-1,sizeof(h));// 初始化头节点cin >> n >> m;for(int i = 0; i < m; i ++){int a,b,c;cin >> a >> b >> c;add(a,b,c);}spfa();if(dist[n] > 0x3f3f3f3f / 2) cout << "impossible" << endl;else cout << dist[n] << endl;
}
这篇关于【算法】spfa算法求最短路（没有负环）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
