本文迁移自六年前的旧博客，部分内容可能已经过时。
原文发布日期：2020-08-20。
最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。
所以今天，我们来研究一下图论中的最短路问题。
什么是最短路？就是在带权图中，寻找从起点到终点所需权值最小的路径。如在：
中寻找从红点到最右侧黄点的最短路。
注意：权值可能为负值.
Floyd
概念
弗洛伊德算法其实是一种动态规划。它可以计算图中任意两点间的最短路径。时间复杂度为O(N3)。一般适合在多元点问题中。好吧，其实实际没什么用。
假设我们已经初始化了邻接矩阵：有边相连则为其权值。没有边权值设为0x3f3f3f3f。那么我们的弗洛伊德就是：
代码
for(int k = 1 ; k <= n ; k ++)
{
for(int i = 1 ; i <= n ; i ++)
{
for(int j = 1 ; j <= n ; j ++)
{
if(dis[i][j] > (dis[i][k] + dis[k][j]) && i != j && i != k && j != k)
{
dis[i][j] = dis[i][k] + dis[k][j];
dis[j][i] = dis[i][k] + dis[k][j];//如果为有向图，这一句不要。
}
}
}
}
最后，dis[i][j]则为i到j的最短路径。
例题
题目描述
题目描述
平面上有n个点(n<=100)，每个点的坐标均在-10000～10000之间。其中的一些点之间有连线。若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。
输入格式
第1行：1个整数n
第2..n+1行：每行2个整数x和y，描述了一个点的坐标
第n+2行：1个整数m，表示图中连线的数量
接下来有m行，每行2个整数i和j，表示第i个点和第j个点之间有连线
最后1行：2个整数s和t，分别表示源点和目标点
输出格式
第1行：1个浮点数，表示从s到t的最短路径长度，保留2位小数（如果到达不了，输出极大值0x7f对应的double类型的值）
样例输入
5
0 0
2 0
2 2
0 2
3 1
5
1 2
1 3
1 4
2 5
3 5
1 5
样例输出
3.41
大致思路
这道题比较简单，就是一道板题，所以直接贴代码了。
但是需要注意的是，这里是还需要求出两点的直线距离，我们可以这样写一个函数求出他的直线距离：
double lon(double x1, double y1, double x2, double y2)
{
double ans;
ans = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
return ans;
}
AC代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#define outn(x) putchar('\n')
#define out(x) putchar(' ')
#define LL long long
using namespace std;
double lon(double x1, double y1, double x2, double y2)
{
double ans;
ans = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
return ans;
}
const int MAXN = 105;
struct node{
double x, y;
}a[MAXN];
int x, y, s, t;
int n, m;
double dis[MAXN][MAXN];
int main()
{
scanf("%d", &n);
for(int i = 1 ; i <= n ; i ++)
{
scanf("%d %d", &x, &y);
a[i].x = x;
a[i].y = y;
}
scanf("%d", &m);
memset(dis, 0x7f, sizeof(dis));
for(int i = 1 ; i <= m ; i ++)
{
scanf("%d %d", &x, &y);
dis[x][y] = lon(a[x].x, a[x].y, a[y].x, a[y].y);
dis[y][x] = lon(a[x].x, a[x].y, a[y].x, a[y].y);
}
for(int k = 1 ; k <= n ; k ++)
{
for(int i = 1 ; i <= n ; i ++)
{
for(int j = 1 ; j <= n ; j ++)
{
if(dis[i][j] > (dis[i][k] + dis[k][j]) && i != j && i != k && j != k)
{
dis[i][j] = dis[i][k] + dis[k][j];
dis[j][i] = dis[i][k] + dis[k][j];
}
}
}
}
scanf("%d %d", &s, &t);
printf("%.2lf", dis[s][t]);
return 0;
}
输出最短路径
有时候，我们还需要输出最短路径。我们可以定义一个pre[i][j]的二维数组记录从i到j的最短路径中，j的前驱点是哪个。最后我们递归还原路径即可。
具体实现：
初始化pre[n][n] = 0，方便递归跳出。然后我们在输入的时候，只需要加上这两条代码重置相连边尾结点：
for(int i = 1 ; i <= m ; i ++)
{
scanf("%d %d %d", &be, &en, &w);
g[be][en] = w;
+ pre[be][en] = w;
+ pre[en][be] = w;
//be = begin, en = end
}
还有一个输出函数：
void print(int x)
{
if(pre[s][x]==0) return;
print(pre[s][x]);
printf("->%d",x);
}
因为这个差别不大，就不给例题了。
Dijkstra
Dijkstra主要思想是把结点分为两组：已经确定最短路（蓝色阵营）和尚未确定最短路（红色阵营）。我们不断从第二组中选择路径长度最短的点放入第一组中并拓展。
注意：Dijkstra只能运用于正权图中。
松弛
首先，我们要先了解“松弛操作”。松弛就是当经过k点比直接连接的所需权值更小时，选择走k点，这就是松弛操作。比如：
描述
首先，我们设起点为s，dis[v]表示从指定起点s到终点v的最短路径，那么我们在使用pre[v]用来输出路径。
模拟
接下来,我们来模拟一下dijkstra的步骤(我们各点的数据在最右):
首先,我们有这样一个图:
这是我们的原始图.然后,我们初始化图:把起点归入蓝色阵营,然后依次松弛:
寻找源点相邻的最短路,发现2号点是最划算的,于是我们把2号点放入蓝色阵营:
继续松弛源点到1/4/3:
然后,寻找源点到1/4/3的最短路,我们发现1号点是最短的,于是乎,我们又把一号点归入蓝色阵营:
接下来,我们从1号点开始继续松弛,松弛源点到4,并把4号点放入蓝色阵营:
然后,由于点4没有相邻点,故不作松弛操作:
最后,松弛4号点旁边的点,并最后把3号点放入蓝色阵营:
邻接矩阵
初始化
memset(dis, INF, sizeof(dis));//INF = 0x3f
memset(vis, 0, sizeof(vis));
for(int i = 1 ; i <= n ; i ++) {
dis[i] = w[s][i];
}
dis[s] = 0;//自己到自己花费0
pre[s] = 0;//推出递推
vis[s] = 0;//自己走过
算法
for(int i = 1 ; i <= n - 1 ; i ++) {
int minn = 0x3f3f3f3f; //最小的路径初始化
int id; //记录最短的id
for(int j = 1 ; j <= n ; j ++) {
if(vis[j] == 0 && dis[j] < minn) {
minn = dis[j];
id = j;` //记录id
}
}
vis[id] = true; //确定最短路,归入蓝点阵营.
for(int j = 1 ; j <= n ; j ++) {
if(dis[id] + w[id][j] < dis[j]) {
dis[j] = dis[id] + w[id][j]; //松弛所有点
}
}
}
注释里已经很详细说明了如何写出邻接矩阵的dijkstra.如果要输出路径,只需这样:
for(int j = 1 ; j <= n ; j ++) {
if(dis[id] + w[id][j] < dis[j]) {
dis[j] = dis[id] + w[id][j]; //松弛所有点
+ pre[j] = id; //用于输出路径
}
}
和这个print:
void print(int x) {
if(pre[x] == 0) return;
print(pre[x]);
printf("%d ", x);
}
邻接表
struct edge{
int v, w; //v = 后继,w = 权值
};
vector<edge> G[MAXN];
void Dijkstra() {
memset(dis, INF, sizeof(dis)); //INF = 0x3f
memset(vis, 0, sizeof(vis));
dis[s] = 0; //自己到自己花费0
for(int i = 1 ; i <= n - 1 ; i ++) {
int minn = 0x3f3f3f3f; //最小的路径初始化.!!!!!注意,这里直接用INF会造成太小的问题.0x3f=63!!
int id = 0; //记录最短的id
for(int j = 1 ; j <= n ; j ++) {
if(vis[j] == 0 && dis[j] < minn) {
minn = dis[j];
id = j; //记录id
}
}
vis[id] = true; //确定最短路,归入蓝点阵营.
for(int j = 0 ; j < G[id].size() ; j ++) { //注意vector是从0开始存的
if(dis[id] + G[id][j].w < dis[G[id][j].v]) {
dis[G[id][j].v] = dis[id] + G[id][j].w; //松弛所有点
}
}
}
}
还有主函数部分:
for(int i = 0 ; i < m ; i ++) {
scanf("%d %d %d", &be, &en, &w);
edge now;
now.v = en;
now.w = w;
G[be].push_back(now);
}
如果要输出路径,我们应该加上:
//位置:dijkstra的最后一个小循环
for(int j = 0 ; j < G[id].size() ; j ++) { //注意vector是从0开始存的
if(dis[id] + G[id][j].w < dis[G[id][j].v]) {
dis[G[id][j].v] = dis[id] + G[id][j].w; //松弛所有点
+ pre[s][G[id][j].v] = pre[id][G[id][j].v]; //用于输出路径
}
}
和主函数:
for (int i = 0; i < m; i++) {
scanf("%d %d %d", &be, &en, &w);
edge now;
now.v = en;
now.w = w;
+ pre[be][en] = be;
G[be].push_back(now);
}
和print:
void print(int x) {
if(pre[s][x] == 0)return;
print(pre[s][x]);
printf("%d ", x);
}
例题:
题目链接:
题目描述
题目描述
有向图的单源点最短路问题（Dijkstra算法）
输入格式
第1行：2个空格分开的整数n(2<=n<=500)和m(10<=m<=20000)，分别表示图的顶点数和边数。
第2..m+1行：每行3个空格分开的整数i，j， w。i表示一条边的起点，j表示终点， w表示权值。
第m＋2行：2个整数s，t(1<=s，t<=n),表示指定的顶点。
输出格式
第1行：最小距离
第2行：最短路径（从起点到终点的序列，用1个空格分开）
样例
样例输入
5 7
1 2 10
1 4 30
1 5 100
2 3 50
3 5 10
4 3 20
4 5 60
1 5
样例输出
60
1 4 3 5
大致思路
额,这道题好像没有思路.就是直接套板子就可以了.我才不会告诉你刚才的板子就是从这道题代码拿的
AC代码之邻接矩阵
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2505;
#define INF 0x3f
int n, m, s, t, be, en, w, pre[MAXN], g[MAXN][MAXN], dis[MAXN], k;
bool vis[MAXN];
void print(int x) {
if (pre[x] == 0)
return;
print(pre[x]);
printf("%d ", x);
}
int main() {
memset(dis, 0x3f, sizeof(dis)); // INF = 0x3f
memset(vis, 0, sizeof(vis));
dis[s] = 0; //自己到自己花费0
pre[s] = 0; //推出递推
vis[s] = 0; //自己走过
scanf("%d %d", &n, &m);
memset(g, 0x3f, sizeof(g));
for (int i = 1; i <= m; i++) {
scanf("%d %d %d", &be, &en, &w);
g[be][en] = w;
}
for (int i = 1; i <= n; i++) {
dis[i] = g[s][i];
}
scanf("%d %d", &s, &t);
dis[s] = 0;
pre[s] = 0;
for (int i = 1; i <= n - 1; i++) {
int minn = 0x3f3f3f3f; //最小的路径初始化
int id; //记录最短的id
for (int j = 1; j <= n; j++) {
if (vis[j] == 0 && dis[j] < minn) {
minn = dis[j];
id = j; //记录id
}
}
vis[id] = true; //确定最短路,归入蓝点阵营.
for (int j = 1; j <= n; j++) {
if (dis[id] + g[id][j] < dis[j]) {
dis[j] = dis[id] + g[id][j]; //松弛所有点
pre[j] = id; //用于输出路径
}
}
}
printf("%d\n%d ", dis[t], s);
print(t);
return 0;
}
AC代码之邻接表
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 505;
#define INF 0x3f
int n, m, s, t, be, en, w, pre[MAXN][MAXN], dis[MAXN], k;
bool vis[MAXN];
void print(int x) {
if(pre[s][x] == 0)return;
print(pre[s][x]);
printf("%d ", x);
}
struct edge{
int v, w; //v = 后继,w = 权值
};
vector<edge> G[MAXN];
void Dijkstra() {
memset(dis, INF, sizeof(dis)); //INF = 0x3f
memset(vis, 0, sizeof(vis));
dis[s] = 0; //自己到自己花费0
for(int i = 1 ; i <= n - 1 ; i ++) {
int minn = 0x3f3f3f3f; //最小的路径初始化.!!!!!注意,这里直接用INF会造成太小的问题.ox3f=63!!
int id = 0; //记录最短的id
for(int j = 1 ; j <= n ; j ++) {
if(vis[j] == 0 && dis[j] < minn) {
minn = dis[j];
id = j; //记录id
}
}
vis[id] = true; //确定最短路,归入蓝点阵营.
for(int j = 0 ; j < G[id].size() ; j ++) { //注意vector是从0开始存的
if(dis[id] + G[id][j].w < dis[G[id][j].v]) {
dis[G[id][j].v] = dis[id] + G[id][j].w; //松弛所有点
pre[s][G[id][j].v] = pre[id][G[id][j].v]; //用于输出路径
}
}
}
}
int main()
{
scanf("%d %d", &n, &m);
for(int i = 0 ; i < m ; i ++) {
scanf("%d %d %d", &be, &en, &w);
edge now;
now.v = en;
now.w = w;
pre[be][en] = be;
G[be].push_back(now);
}
scanf("%d %d", &s, &t);
Dijkstra();
printf("%d\n%d ", dis[t], s);
print(t);
return 0;
}
负权图的思考
我们在这里就已经讲过Dijkstra不能用于负权图,但是为什么呢?这里我们可以举一个例子:
我们可以发现,在这里最短路应该是0->2->3->4,但是正常操作我们应该是在这个3更新4的时候,发现4已经是蓝点所以就会不更新,也就是最后最短路其实是0->2->1->4.这很明显是不对的,所以Dijkstra是不能应用在负权图的.
Bellman-Ford
刚才我们说Dijkstra是不能使用负权图的,那么有什么可以代替呢?当然,弗洛伊德是可以的.但是,我们还有一种Bellman-Ford.它是以边为阶段的一种算法.一般来说,他是每次操作对所有的边进行松弛,松弛n-1次.为什么是n-1次呢?是因为如果我们有这样一个图的话:
他就刚好是n-1条边,也就是松弛n-1次.
注意,这个算法可以运用于负权图.
初始化
memset(dis, 0x3f, sizeof(dis));
dis[s] = 0;
核心代码
for(int i = 1 ; i <= nodenum - 1 ; i ++) {
for(int j = 1 ; j <= edgenum ; j ++) {
if(dist[en] > dist[be] + w) {//送松弛
dist[en] = dist[be] + w;
pre[en] = be;//输出路径
}
}
}
接下来,我们来具体演示一下
这是我们的原图.各数据如下：
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ |
然后，我们刚才说，Bellman-Ford是以边为阶段的，所以我们下一步，就是对第一条边双向进行松弛：
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 0 | 1 | ∞ | ∞ | ∞ | ∞ |
然后，我们对第二条边双向松弛：
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 0 | 1 | ∞ | ∞ | ∞ | ∞ |
随后,对于第三条边双向松弛:
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 0 | 1 | 2 | ∞ | ∞ | ∞ |
随后,对于第四条边进行双向松弛:
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 0 | 1 | 2 | 5 | ∞ | ∞ |
对于第五条边双向松弛:
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 0 | 1 | 2 | 5 | 10 | ∞ |
对于第六条边双向松弛:
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 0 | 1 | 2 | 5 | 8 | ∞ |
对于第七条边双向松弛:
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 0 | 1 | 2 | 5 | 8 | 11 |
最后, 对于第八条边双向松弛:
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 0 | 1 | 2 | 5 | 8 | 11 |
至此,一次Bellman-Ford就完成了.
负权图
我们说,Bellman-Ford是可以适用于有向负权图的.那么我们来举一个无向的例子:
双向
这,就是一个负权图.
初始化:
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ |
我们对于第一条边双向松弛:
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 0 | 1 | ∞ | ∞ | ∞ | ∞ |
对于第二条边双向松弛:
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 0 | 1 | 2 | ∞ | ∞ | ∞ |
对于第三条边双向松弛:
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 0 | -5 | -2 | ∞ | ∞ | ∞ |
在这里我们可以发现已经有问题了.我们甚至可以2->3->2->3->2......不断松弛,这是个死循环.所以,我们已经证明Bellman-Ford不适用于双向负权图.
单向(有向)
既然双向图不行,那么有向图呢?我们把图改为有向图,并对于第三条双向松弛:
双向松弛并不代表均会松弛,可能会有失败的.
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 0 | -1 | 2 | ∞ | ∞ | ∞ |
对于第四条边双向松弛:
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 0 | -1 | 2 | 3 | ∞ | ∞ |
对于第五条双向进行松弛:
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 0 | -1 | 2 | 3 | 8 | ∞ |
对于第六条边双向进行松弛:
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 0 | -1 | 2 | 3 | 8 | ∞ |
对于第七条边双向松弛:
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 0 | -1 | 2 | 3 | 8 | 10 |
The last,对于第八条边双向松弛:
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 0 | -1 | 2 | 3 | 8 | 10 |
接下来,就是实际代码了:
例题<单源点最短路问题-2>
题目描述
题目描述
有向图负权的单源点最短路问题（BellmanFord算法）
输入格式
第1行：2个空格分开的整数n(2<=n<=500)和m(10<=m<=20000)，分别表示图的顶点数和边数。
第2..m+1行：每行3个空格分开的整数i，j， w。i表示一条边的起点，j表示终点， w表示权值。
第m＋2行：2个整数s，t(1<=s，t<=n),表示指定的顶点。
输出格式
第1行：最小距离
第2行：最短路径（从起点到终点的序列，用1个空格分开）
如果出现负权回路,输出:No Solution
样例
样例输入1
6 7
1 2 2
1 3 -1
2 4 -3
3 4 3
3 6 7
4 6 -2
3 5 6
1 6
样例输出1
-3
1 2 4 6
样例输入2
3 3
1 2 -7
2 3 4
3 1 2
1 3
样例输出2
No Solution
数据范围与提示
如果最短路径有多条,输出路径经过边数较小的解; 如果最短路径边数相同,输出编号较小的序列.
AC代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 505;
const int MAXNEDGE = 20005;
int min(int x, int y)
{
return x < y ? x : y;
}
//be = begin; en = end ;inde = index
int edgenum, nodenum, inde, que, pre[MAXN];
void print(int x) {
if(pre[x] == 0){
cout<<x<<" ";
return;
}
print(pre[x]);
printf("%d ", x);
}
typedef struct Edge{
int be, en, w;//begin为起点,end为重点
}Edge;
Edge edge[MAXNEDGE];
int dist[MAXNEDGE];
void relax(int be, int en, int w) {
if(dist[en] > dist[be] + w) {//满足松弛条件
dist[en] = dist[be] + w;
pre[en] = be;//用于输出路径
}
if(dist[en] == dist[be] + w)
{
pre[en] = min(be,pre[en]);//同上
}
}
bool bf(){
for(int i = 1 ; i <= nodenum - 1 ; i ++) {
for(int j = 1 ; j <= edgenum ; j ++) {
relax(edge[j].be, edge[j].en, edge[j].w);//初始松弛
}
}
for(int i = 1 ; i <= edgenum ; i ++) {
if(dist[edge[i].en] > dist[edge[i].be] + edge[i].w) {//确定是否有负环.即再跑一遍,如还能松弛,则代表有负环.
return 0;
}
}
return 1;
}
int main()
{
memset(dist, 0x3f, sizeof(dist));
scanf("%d %d", &nodenum, &edgenum);//输入点的数和边的数.
for(int i = 1 ; i <= edgenum ; i ++){
scanf("%d %d %d", &edge[i].be, &edge[i].en, &edge[i].w);//依次输入
}
scanf ("%d %d", &inde, &que);//起点和终点
dist[inde] = 0;//起点标记
for(int i = 1 ; i <= edgenum ; i ++) {
if(edge[i].be == inde) {
dist[edge[i].en] = edge[i].w;//首先松弛与起点衔接的点
}
}
bool ans = bf();
if(ans == false){
printf("No Solution");
return 0;
}
printf("%d\n%d ", dist[que],inde);
print(que);
return 0;
}
SPFA
我们前面已经学习了BellmanFord.但是我们可以发现,很多松弛是无效的.那么SPFA算法可以说是对于BellmanFord算法的优化罢了.也可以是队列优化.
SPFA算法的全称是：Shortest Path Faster Algorithm，是西南交通大学段凡丁于 1994 年发表的论文中的名字。不过，段凡丁的证明是错误的，且在 Bellman-Ford 算法提出后不久（1957 年）已有队列优化内容，所以国际上不承认 SPFA 算法是段凡丁提出的。–百度百科
大致思路
我们主要是这样:
就是bfs的思路,取出源点,放入队列,弹出点,放入相邻点,如此往复直到队列为空.
那么我们怎么判断负环呢?就是当某个点进入队列的次数超过n次即可.
这个是大致的思路
接下来,我们来具体模拟一下.
模拟
这,是我们的图:
这,是我们的队列.
| 入队元素 | a |
|---|---|
| 元素值 | 0 |
按照我们的流程,首先队列不为空,所以应该把a出队,并单独松弛.成功b,c,d三点,且都不在队列,所以全部加入队列:
| 入队元素 | b | c | d |
|---|---|---|---|
| 元素值 | 24 | 8 | 15 |
然后队首元素b出队,且松弛其邻接点e,e不在队列,所以将其加入队列:
| 入队元素 | c | d | e |
|---|---|---|---|
| 元素值 | 8 | 15 | 30 |
然后队首元素c出队,且松弛其邻接点e,f.但是由于e已经在队列中,所以不再入队,只入队f.
| 入队元素 | d | e | f |
|---|---|---|---|
| 元素值 | 15 | 15 | 11 |
队首元素d出队,松弛邻接点g,并成功入队:
| 入队元素 | e | f | g |
|---|---|---|---|
| 元素值 | 15 | 11 | 19 |
随后e出队,但是松弛e失败.图就不放了.
| 入队元素 | f | g |
|---|---|---|
| 元素值 | 11 | 19 |
f出队,松弛d和g和e,但是只成功了g和e,又因为g在队列里,所以不入队,只更新. e因为不在队列(注意是考虑是否在当前队列,而不是考虑是否出现过.),所以需要入队:
| 入队元素 | g | e |
|---|---|---|
| 元素值 | 14 | 13 |
然后取出g,松弛b,并加入队列:
| 入队元素 | e | b |
|---|---|---|
| 元素值 | 13 | 17 |
e出队,松弛g,失败,图未变:
| 入队元素 | b |
|---|---|
| 元素值 | 13 |
取出b,松弛e失败.此时队列已空,算法结束,a~g最短路为14,其余a~n最短路如图.
模板代码
这个就直接看例题了.
例题
题目描述
有向图的单源点最短路径问题。源点编号为1，终点编号为n。
输入格式
第1行：2个空格分开的整数n(2<=n<=5000)和m(10<=m<=500000)，分别表示图的顶点数和边数。
第2..m+1行：每行3个空格分开的整数i，j， w。i表示一条边的起点，j表示终点， w表示权值。
输出格式
第1行：1个整数，表示最小距离
样例一输入
4 7
1 2 68
1 3 19
1 4 66
2 3 23
3 4 65
3 2 57
4 1 68
样例一输出
66
样例二输入
3 3
1 2 -7
2 3 4
3 1 2
样例二输出
No Solution
AC代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 7e5 + 5;
int n, m, ans, dis[MAXN], s, e, num[MAXN];
bool vis[MAXN];
struct Node{
int v, w;
};
vector<Node> node[MAXN];
void init() {
for(int i = 1 ; i <= m ; i ++) {
Node tmp;
int u;
scanf("%d %d %d", &u, &tmp.v, &tmp.w);//输入
node[u].push_back(tmp);//输入
}
memset(dis, 0x3f, sizeof(dis));//初始化dis
}
bool SPFA() {
queue<int> q;
dis[s] = 0;//起点最短路为0
vis[s] = 1;//起点标记已走
q.push(s);
while(!q.empty()) {
int p = q.front();
q.pop();//取出最顶点
vis[p]= 0;//去除的点取消在队列的标记
int siz = node[p].size();
for(int i = 0 ; i < siz ; i ++) {
int v = node[p][i].v;
int w = node[p][i].w;
if(dis[v] > dis[p] + w) {
dis[v] = dis[p] + w;
num[v]++;
if(num[v] > n) {//有负环
return false;
}
if(!vis[v]) {//没在队列
vis[v] = 1;
q.push(v);
}
}
}
}
return true;
}
int main() {
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
scanf("%d %d", &n, &m);
init();//初始化
s = 1;
e = n;//这两行是因为这道题制定了起点终点，平时用需要输入.
if(!SPFA()) {
printf("No Solution");
return 0;
}
printf("%d", dis[e]);//如果输出路径，用一个pre
return 0;
}
一些其他的东西
现在最短路就即将告一段落了.但是,我还想再讨论一些东西.
题目
首先,在条件允许情况下,如果想全面测试自己的代码,可以去STZOJ交一下:
对于其他的上面的例题,题目也都在这里:
关于SPFA的一些事
经常看到一种言论:SPFA已死.这是为什么呢?因为很好卡SPFA.我们都知道SPFA的时间复杂度是不稳定的,一般情况是比较节约时间的,但是在极端情况下会退化到bellman-ford的时间.所以在蓝书(算法竞赛进阶指南)上也说明必须谨慎使用.但是,真的是这样吗?
那么哪种图会卡SPFA呢?举一个例子:菊花链状图.菊花链状图可以看这篇:
我们使用里面的对拍代码来分别运行三种代码(没有Floyd):
数据:n=10000,m=19998.
使用HP一体机评测,单开,Windows10 1909,处理器i5-9500T.编译器Dev-cpp.
以下是时间数据:
有向无环图
| 算法名称 | SPFA | Bellman-Ford | Dijkstra |
|---|---|---|---|
| 时间 | 0.2291 seconds | 3.176 seconds | 0.6916 seconds |
有向负环图:
| 算法名称 | SPFA | Bellman-Ford |
|---|---|---|
| 时间 | 0.9138 seconds | 240.2 seconds(int爆了的用时)320.5 seconds(long long) |
可以看见,即使是这种图,SPFA也占有很强的时间优势.有知道为什么的可以评论一下.那么普通图呢?
| 算法名称 | SPFA | Bellman-Ford | Dijkstra |
|---|---|---|---|
| 时间 | 0.3554 seconds | 210.2 seconds | 39.78 seconds |
这个差距就更加明显了.
Comments NOTHING