题目描述
如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。
输入输出格式
输入格式：
第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。
接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度。
输出格式：
一行，包含N个用空格分隔的整数，其中第i个整数表示从点S出发到点i的最短路径长度（若S=i则最短路径长度为0，若从点S无法到达点i，则最短路径长度为2147483647）
输入输出样例
输入样例#1：
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
输出样例#1：
0 2 4 3
1.SPFA的描述
SPFA（Shortest Path Faster Algorithm）（队列优化）算法是求单源最短路径的一种算法，它还有一个重要的功能是判负环（在差分约束系统中会得以体现），在Bellman-ford算法的基础上加上一个队列优化，减少了冗余的松弛操作，是一种高效的最短路算法。SPFA算法由段凡丁于1994年西安交通大学提出。
2.SPFA算法过程
算法过程分为两步
1.初始化
2.松弛操作
a)初始化过程
将未特别说明的数据设置为正无穷（int最大值2147483647）。
i=j时，它到它自己的边权为0，无向边的数据直接更新为正无穷，在后面的代码实现时，我们可以进行对比更新。
b)松弛操作
初始化源点数据，设置一个dis数组，inq数组，q队列。
dis用于存最小路径，inq判断当点是否在队列内，q用于存待松弛的边。
第一个压入q队列的数据为源点1。
进入核心循环代码。
取出队列顶数据，为待松弛的边。
之后进行遍历，spfa的核心就是过一点的距离+该点长度小于末点的dis值，就更新末点的dis。
接着继续判断没有访问过的边，加入待松弛队列。
最后直接输出dis数组数据即为最小路径。
代码实现
#include<vector>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
#include<list>
using namespace std;
const int maxn = 500000 + 10;
struct nodes {
int u, to, w;
};//to表示末点，w表示长度
int dis[10000 + 20];
typedef struct nodes node;//方便后面的定义。。
list<node> v[10000 + 20];//边集，list和vector都可以。。
int n, m, s;
int inq[10000 + 20]; //用inq来表示点是否在queue中，判重和记忆。。
queue<int> q;//不解释了、、
int main()
{
cin >> n >> m >> s;
for (int i = 0; i < m; i++) {
int x, y, z;
cin >> x >> y >> z;
v[x].push_back({ x,y,z }); //用list来读入边集
}
for (int i = 0; i < 10000 + 20; i++) dis[i] = 2147483647; //初始化的时候 dis全部是2147483647，而是dis[s]=0；这个在输出的时候有用。。
dis[s] = 0;
q.push(s);
inq[s] = 1; //用来判断点是否在队列里面，，类似记忆。。
while (!q.empty()) {
int cur = q.front(); q.pop();//取出待松弛的边
inq[cur] = 0;
for (list<node>::iterator it = v[cur].begin(); it != v[cur].end(); it++) {//遍历
if (dis[cur] + it->w < dis[it->to]) {//这个是松弛操作的核心。。如果过一点的距离+该点长度小于末点的dis值，就更新末点的dis
dis[it->to] = dis[cur] + it->w;
if (!inq[it->to]) {//判断是否in queue
q.push(it->to);//松弛之后，加入queue，等待接下来的松弛。。
}
}
}
}
for (int i = 1; i <= n; i++) {
cout << dis[i] << " ";
}
return 0;
}
网友评论