最短路

1 简介

最短路问题分为两类:单源最短路多源最短路。前者只需要求一个固定的起点到各个顶点的最短路径,后者则要求得出任意两个顶点之间的最短路径。

  • 单源 Dijkstra算法
    • 优点:时间复杂度稳定O(n2)O(n^2),堆优化能达到O(ElogE)O(ElogE);也可解决多源最短路,总的时间复杂度也是O(n3)O(n^3)
    • 缺点:不能处理负边
  • 单源 Bellman-Ford算法
    • 优点:其优于Dijkstra算法的方面是边的权值可以为负数、实现简单
    • 缺点:时间复杂度过高,高达O(VE)O(V*E);但算法可以进行若干种优化,提高了效率。
  • 单源 SPFA算法
    • 优点:快于Bellman-Ford,据说随机数据下期望时间复杂度是O(m+nlogn)O(m+nlogn)
    • 缺点:时间复杂度不稳定,最坏情况可以被卡成Bellman-Ford,也就是O(VE)O(V*E)
  • 全源 Floyd算法
    • 优点:算法简洁,可以解决负权图
    • 缺点:时间复杂度为O(n3)O(n^3),空间复杂度为O(n2)O(n^2),都比较高,所以只适用于数据规模较小的情形;不能解决负环图
  • 全源 Johnson算法
    • 优点:相对于Floyd算法时间复杂度低,O(nmlogm)O(nmlogm)
    • 缺点:无负环图、算法较繁琐
  • BFS算法
    • 优点
    • 缺点:只能解决无权图

2 单源 Dijkstra算法

贪心的思想,不断取出离顶点最近没有被访问过的点,松弛它和它能到达的所有点。

对于每个顶点v∈V,都设置一个属性d[v],用来描述从源点s到v的最短路径上权值的上界,称为最短路径估计(shortest-pathestimate)。

π[v]代表S到v的当前最短路径中v点之前的一个点的编号,我们用下面的Θ(V)时间的过程来对最短路径估计和前趋进行初始化。

在松弛一条边(u,v)的过程中,要测试是否可以通过u,对迄今找到的v的最短路径进行改进;如果可以改进的话,则更新d[v]和π[v]。一次松弛操作可以减小最短路径估计的值d[v],并更新v的前趋域π[v](S到v的当前最短路径中v点之前的一个点的编号)。

打印路径:只需要用一个pre[]数组存储每个点的父节点即可。(单源最短路的起点是固定的,所以每条路有且仅有一个祖先节点,一步步溯源上去的路径是唯一的。相反,这里不能存子节点,因为从源点下去,有很多条最短路径)

参考:https://zhuanlan.zhihu.com/p/96621396

朴素Dijkstra:时间复杂度是 O(n2+m)O(n^2+m), nn 表示点数,mm 表示边数

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
const int maxn = 5e2 + 5;

int g[maxn][maxn]; // 存储每条边
int dist[maxn]; // 存储1号点到每个点的最短距离
bool st[maxn]; // 存储每个点的最短路是否已经确定
int n;//点数

// 求1号点到n号点的最短路,如果不存在则返回-1
int dijkstra() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;

for (int i = 0; i < n - 1; i ++ ) {
int t = -1; // 在还未确定最短路的点中,寻找距离最小的点
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;

// 用t更新其他点的距离
for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]);

st[t] = true;
}

if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}

堆优化Dijkstra:时间复杂度 O(mlogn)O(mlogn), nn 表示点数,mm 表示边数

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
const int maxn = 1.5e5 + 5;
typedef pair<int, int> PII;

int n; // 点的数量
int h[maxn], w[maxn], e[maxn], ne[maxn], idx; // 邻接表存储所有边
int dist[maxn]; // 存储所有点到1号点的距离
bool st[maxn]; // 存储每个点的最短距离是否已确定
//加边
void add(int x, int y, int c) {
w[idx] = c; // 有重边也不要紧,假设1->2有权重为2和3的边,再遍历到点1的时候2号点的距离会更新两次放入堆中
e[idx] = y; // 这样堆中会有很多冗余的点,但是在弹出的时候还是会弹出最小值2+x(x为之前确定的最短路径),并
ne[idx] = h[x]; // 标记st为true,所以下一次弹出3+x会continue不会向下执行。
h[x] = idx++;
}
// 求1号点到n号点的最短距离,如果不存在,则返回-1
int dijkstra() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1}); // first存储距离,second存储节点编号

while (heap.size()) {
auto t = heap.top();
heap.pop();

int ver = t.second, distance = t.first;

if (st[ver]) continue;
st[ver] = true;

for (int i = h[ver]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > distance + w[i]) {
dist[j] = distance + w[i];
heap.push({dist[j], j});
}
}
}

if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}

3 单源 Bellman-Ford算法

一维数组dist[]来存储每个点到起点的距离,初始化dist[S] = 0,其他初始化为INF。

找到从起点到某个点的最短路,设起点为S,终点为D,那这条最短路一定是S>P1>P2>...>DS->P_1->P_2->...->D的形式,假设没有负权环,那这条路径上的点的总个数一定不大于n

定义对点x, y的松弛操作是:

1
dist[y] = min(dist[y], dist[x] + e[x][y]);//这里的e[x][y]表示x、y之间的距离,具体形式可能根据存图方法不同而改变

松弛操作就相当于考察能否经由x点使起点到y点的距离变短。

所以要找到最短路,只需要进行以下步骤:

  1. 先松弛SS, P1P_1,此时dist[P1]dist[P_1]必然等于e[S][P1]e[S][P_1]
  2. 再松弛P1,P2P_1, P_2,因为S>P1>P2S->P_1->P_2是最短路的一部分,最短路的子路也是最短路(这是显然的),所以dist[P2]dist[P_2]不可能小于dist[P1]+e[P1][P2]dist[P_1]+e[P_1][P_2],因此它会被更新为dist[P1]+e[P1][P2]dist[P1]+e[P1][P2],即e[S][P1]+e[P1][P2]e[S][P1]+e[P1][P2]
  3. 再松弛P2,P3P2, P3,……以此类推,最终dist[D]dist[D]必然等于e[S][P1]+e[P1][P2]+...e[S][P1]+e[P1][P2]+...,这恰好就是最短路径。

把所有边松弛n-1遍!

https://zhuanlan.zhihu.com/p/96621396

https://blog.csdn.net/luomingjun12315/article/details/50377525

4 单源 SPFA算法

SPFA算法,也就是队列优化的Bellman-Ford算法,维护一个队列。

5 全源 Floyd算法

求出每一对顶点之间的最短路径。Floyd本质上是一个动态规划的思想,每一次循环更新经由k点,i到j的最短路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 算法结束后,d[a][b]表示a到b的最短距离,path存放路径信息
void floyd() {
// 初始化:
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if (i == j) d[i][j] = 0;
else d[i][j] = inf;
//memset(path, -1, sizeof path);

//dp
for (int k = 1; k <= n; k ++ ) {//考虑以k为中转点
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= n; j ++ ) {
if (d[i][j] > d[i][k] + d[k][j]) {//以k为中转点的路径更短
d[i][j] = d[i][k] + d[k][j];//更新最短路径长度
//path[i][j] = k;//中转点
}
}
}
}
}

6 全源 Johnson算法

7 BFS算法

该算法求单源最短路径只适用于无权图,或所有边的权值都相同的图。

练习

  1. acwing模板题目——Dijkstra求最短路 I
  2. Dijkstra求最短路 II