最短路径专题 | Wuhaoda's Blog

最短路径专题

写在前面

之前一直习惯使用SPFA(虽然现在忘得差不多了)
现在学习下堆优化的dijkstra
发现真的比想象中的简单多了
不过还是全部总结下吧

堆优化的dijkstra:

对于不含负权的有向图,这是目前已知的最快的单源最短路径算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <utility>
#define R register
#define C getchar()
#define maxn 100010
#define maxm 200010
using namespace std;

struct Edge {
int next, to, w;
} edge[maxm];

priority_queue< pair<int, int> > q;
int vis[maxn], dis[maxn], head[maxn];
int n, m, s, u, v, w, num;

template <typename T>
inline void read(T &s) {
s = 0;
T f = 1;
char ch = C;
for(; ch > '9' || ch < '0'; ch = C)
if(ch == '-')
f = -1;
for(; ch >= '0' && ch <= '9'; ch = C)
s = (s << 1) + (s << 3) + (ch ^ 48);
s * = f;
}

inline void add(int from, int to, int w) {
edge[++num].next = head[from];
edge[num].to = to;
edge[num].w = w;
head[from] = num;
}

inline void dijkstra() {
for(R int i = 1; i <= n; ++i) {
dis[i] = 2147483647;
vis[i] = 0;
}
dis[s] = 0;
q.push(make_pair(0, s));
while(q.size()) {
int x = q.top().second;
q.pop();
if(vis[x]) continue;
vis[x] = 1;
for(R int i = head[x]; i; i = edge[i].next) {
int y = edge[i].to, z = edge[i].w;
if(dis[y] > dis[x] + z) {
dis[y] = dis[x] + z;
q.push(make_pair(-dis[y], y));
}
}
}
}

int main() {
read(n), read(m), read(s);
for(R int i = 1; i <= m; ++i) {
read(u), read(v), read(w);
add(u, v, w);
}
dijkstra();
for(R int i = 1; i <= n; ++i)
printf("%d ", dis[i]);
return 0;
}

代码中使用了二元组pair
第一维存dis的相反数 第二维存编号
STL大法好

SPFA算法

用于求解有向带权图单源最短路径的改良的贝尔曼-福特算法。这一算法被认为在随机的稀疏图上表现出色,并且极其适合带有负边权的图
容易被卡,尽量少用。
这是用spfa判断负环的方法:
https://www.cnblogs.com/polebug/p/3907847.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void spfa() {
memset(d, 0x3f, sizeof());
memset(d, 0, sizeof());
d[1] = 0; v[1] = 1;
q.push(1);
while(q.size()) {
int x = q.front();
q.pop();
v[x] = 0;
for(int i = head[x]; i; i = edge[i].next) {
int y = edge[i].to, z = edge[i].dis;
if(d[y] > d[x] + z) {
d[y] = d[x] + z;
if(!v[y])
q.push(y), v[y] = 1;
}
}
}
}

题目是洛谷的单源最短路径的板子
这里是链接:
https://www.luogu.org/problemnew/show/P4779

Floyd算法

它对图的要求是:可以是无向图或有向图
边权可正可负,唯一的要求是不能有负环
复杂度O(n^2) 极易超时

1
2
3
4
5
for(k = 1; k <= n; k++)
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
if((d[i][k] != INF) && (d[k][j] != INF) && (d[i][j] + d[k][j] < d[i][j]))
d[i][j] = d[i][j] + d[k][j];