前言
前置知识
正文
单源最短路
单源最短路径问题 (Single Source Shortest Path, SSSP 问题) 是说，给你一张有向图 G = (V, E)，V 是点集，E 是边集，|V| = n, |E| = m，节点以 [1, n]之间的连续整数编号，(x, y, z) 描述一条从 x 出发， 到达 y，长度 / 边权为 z 的有向边。设 1 号点为起点，求长度为 n 的数组 dist，其中 dist[i] 表示从起点 1 到 节点 i 的最短路径的长度。
Dijkstra 算法
Dijkstra 算法的流程如下：
- 初始化 dis[1] = 0，其余节点的 dis 值均为正无穷大。
- 找出一个未被标记的、 dis[x] 最小的节点 x，然后标记节点 x。
- 扫描节点 x 的所有出边 (x, y, z)，若 dis[y] > dis[x] + z，则使用 dis[x] + z 更新 dis[y]。
- 重复上述 2~3 两个步骤，直到所有节点都被标记。
Dijkstra 算法采用贪心策略，仅用于解决带非负权图的单源最短路问题。
当边长 z 都是非负数时，全局最小值不可能再被其他节点更新，故在第 1 步中选出的节点 x 必然满足：dis[x] 已经是起点到 x 的最短路径。
实现
以下是朴素算法的实现示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| struct edge {
int v, w;
};
vector<edge> e[MAXN];
int dis[MAXN], vis[MAXN];
void dijkstra(int n, int s) {
memset(dis, 0x3f, (n + 1) * sizeof(int));
dis[s] = 0;
for (int i = 1; i <= n; i++) {
int u = 0, mind = 0x3f3f3f3f;
for (int j = 1; j <= n; j++)
if(!vis[j] && dis[j] < mind) u = j, mind = dis[j];
vis[u] = true;
for (auto ed : e[u]) {
int v = ed.v, w = ed.w;
if(dis[v] > dis[u] + w) dis[v] = dis[u] + w;
}
}
}
|
上面程序的时间复杂度为 O(n2)
如果我们使用优先队列来维护 dis 数组，则可在 O(mlog n) 的复杂度下实现，代码如下：
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
| struct edge {
int v, w;
};
struct node {
int dis, u;
bool operator>(const node& a) const { return dis > a.dis; }
};
vector<edge> e[MAXN];
int dis[MAXN], vis[MAXN];
priority_queue<node, vector<node>, greater<node>> q;
void dijkstra(int n, int s) {
memset(dis, 0x3f, (n + 1) * sizeof(int));
memset(vis, 0, (n + 1) * sizeof(int));
dis[s] = 0;
q.push({0, s});
while (!q.empty()) {
int u = q.top().u;
q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (auto ed : e[u]) {
int v = ed.v, w = ed.w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.push({dis[v], v});
}
}
}
}
|
Bellman–Ford 算法
Bellman–Ford 算法是一种基于松弛 (relax) 操作的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进行判断。
对于一条边 (u, v)，有以下松弛操作：dis(v) = min(dis(v), dis(u) + w(u, v));
Bellman-Ford 算法所做的，就是不断尝试对图上每一条边进行松弛。
即遵循以下流程：
- 扫描所有边 (u, v, w), 若 dis(v) > dis (u) + w(u, v)，则用 dis (u) + w(u, v) 的值更新 dis(u)。
- 重复上述步骤，直到无法更新。
在最短路存在的情况下，由于一次松弛操作会使最短路的边数至少 + 1，而最短路的边数最多为 n - 1，因此整个算法最多执行 n - 1 轮松弛操作。故总时间复杂度为 O(nm)。
实现
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
| struct Edge {
int u, v, w;
};
vector<Edge> edge;
int dis[MAXN], u, v, w;
constexpr int INF = 0x3f3f3f3f;
bool bellmanford(int n, int s) {
memset(dis, 0x3f, (n + 1) * sizeof(int));
dis[s] = 0;
bool flag = false;
for (int i = 1; i <= n; i++) {
flag = false;
for (int j = 0; j < edge.size(); j++) {
u = edge[j].u, v = edge[j].v, w = edge[j].w;
if (dis[u] == INF) continue;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
flag = true;
}
}
if (!flag) {
break;
}
}
return flag;
}
|
SPFA 算法
SPFA 算法即是“队列优化的 Bellman-Ford 算法”。
流程如下：
- 建立一个队列，最初队列仅包含起点
- 取出队头节点 u，扫描它的所有出边 (u, v, w)，若 dis(v) > dis (u) + w(u, v)，则用 dis (u) + w(u, v) 的值更新 dis(u)。同时，若 v 不在队列中，则把 v 入队。
- 重复上述步骤，直到队列为空。
以下是 SPFA 算法的实现：
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
| struct edge {
int v, w;
};
vector<edge> e[MAXN];
int dis[MAXN], cnt[MAXN], vis[MAXN];
queue<int> q;
bool spfa(int n, int s) {
memset(dis, 0x3f, (n + 1) * sizeof(int));
dis[s] = 0, vis[s] = 1;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop(), vis[u] = 0;
for (auto ed : e[u]) {
int v = ed.v, w = ed.w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
cnt[v] = cnt[u] + 1;
if (cnt[v] >= n) return false;
if (!vis[v]) q.push(v), vis[v] = 1;
}
}
}
return true;
}
|
任意两点间最短路径
Floyd 算法
适用任何图
我们令 f[x][y] 表示 x 到 y 的最短路径，满足任意一个点 k，有 f[x][y] = min(f[x][y], f[x][k] + f[k][y])。
因为我们引进了点 k，所以该算法的复杂度为 O(n3)。
以下是 Floyd 算法的实现方式：
1
2
3
4
5
6
7
| for (k = 1; k <= n; k++) {
for (x = 1; x <= n; x++) {
for (y = 1; y <= n; y++) {
f[x][y] = min(f[x][y], f[x][k] + f[k][y]);
}
}
}
|