6.5 最短路径

BFS 求非带权最短路径，Dijkstra 单源最短路径算法，Floyd 各顶点间最短路径算法，以及它们的适用条件。

最短路径问题

当图是带权图时，把从一个顶点 $v_0$ 到图中其余任意一个顶点 $v_i$ 的一条路径（可能不止一条）所经过边上的权值之和，定义为该路径的带权路径长度，把带权路径长度最短的那条路径称为最短路径。

求解最短路径的算法通常都依赖于一种性质，即两点之间的最短路径也包含了路径上其他顶点间的最短路径。带权有向图 $G$ 的最短路径问题一般可分为两类：

• 单源最短路径：求图中某一顶点到其他各顶点的最短路径，可通过经典的 Dijkstra 算法求解；
• 每对顶点间的最短路径：可通过 Floyd 算法来求解。

对于不带权的图（或各边权值相同），使用 BFS 即可求出单源最短路径（见上一课）。

Dijkstra 算法

Dijkstra（迪杰斯特拉）算法设置一个集合 $S$ 记录已求得的最短路径的顶点，初始时把源点 $v_0$ 放入 $S$，集合 $S$ 每并入一个新顶点 $v_i$，都要修改源点 $v_0$ 到集合 $V - S$ 中顶点当前的最短路径长度值。

在构造的过程中还设置了三个辅助数组：

• final[]：标记各顶点是否已找到最短路径，即是否归入集合 $S$；
• dist[]：记录从源点 $v_0$ 到其他各顶点当前的最短路径长度，它的初态为：若从 $v_0$ 到 $v_i$ 有弧，则 dist[i] 为弧上的权值；否则置 dist[i] 为 ∞；
• path[]：path[i] 表示从源点到顶点 $i$ 之间的最短路径的前驱结点。在算法结束时，可根据其值追溯得到源点 $v_0$ 到顶点 $v_i$ 的最短路径。

1void Dijkstra(Graph G, int v0) {
2    for (每个顶点 i) {             // 初始化
3        final[i] = false;
4        dist[i] = G.arcs[v0][i];   // 无边则为 ∞
5        path[i] = (dist[i] < ∞) ? v0 : -1;
6    }
7    final[v0] = true; dist[v0] = 0;
8    for (n - 1 轮) {
9        选出 final[u] == false 且 dist[u] 最小的顶点 u;
10        final[u] = true;           // u 的最短路径已确定
11        for (u 的每个邻接点 w)
12            if (!final[w] && dist[u] + arcs[u][w] < dist[w]) {
13                dist[w] = dist[u] + arcs[u][w];
14                path[w] = u;       // 修改前驱
15            }
16    }
17}

以源点 1 为例，各轮结果如下：

时间复杂度：使用邻接矩阵表示时，时间复杂度为 $O(|V|^2)$；使用带权的邻接表表示时，虽然修改 dist[] 的时间可以减少，但由于在 dist[] 中选择最小分量的时间不变，所以时间复杂度仍为 $O(|V|^2)$。人们可能只希望找到从源点到某个特定顶点的最短路径，但这个问题和求解源点到其他所有顶点的最短路径一样复杂，时间复杂度也为 $O(|V|^2)$。

Floyd 算法

Floyd（弗洛伊德）算法求各顶点之间最短路径的基本思想是：递推产生一个 $n$ 阶方阵序列 $A^{(-1)}, A^{(0)}, \ldots, A^{(k)}, \ldots, A^{(n-1)}$，其中 $A^{(k)}[i][j]$ 表示从顶点 $v_i$ 到顶点 $v_j$ 的路径长度，$k$ 表示绕行第 $k$ 个顶点的运算步骤。

初始时，对于任意两个顶点 $v_i$ 和 $v_j$，若它们之间存在边，则以此边上的权值作为它们之间的最短路径长度；若它们之间不存在有向边，则以 ∞ 作为它们之间的最短路径长度。以后逐步尝试在原路径中加入顶点 $k$（$k = 0, 1, \ldots, n-1$）作为中间顶点。若增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径：

1void Floyd(Graph G) {
2    // 初始化：A[i][j] = arcs[i][j]，path[i][j] = -1
3    for (int k = 0; k < n; k++)        // 考虑以 Vk 作为中转点
4        for (int i = 0; i < n; i++)
5            for (int j = 0; j < n; j++)
6                if (A[i][k] + A[k][j] < A[i][j]) {
7                    A[i][j] = A[i][k] + A[k][j];
8                    path[i][j] = k;    // 中转点
9                }
10}

• Floyd 算法的时间复杂度为 $O(|V|^3)$。不过由于其代码很紧凑，且并不包含其他复杂的数据结构，因此隐含的常数系数是很小的，即使对于中等规模的输入来说，它仍然是相当有效的。
• Floyd 算法允许图中有带负权值的边，但不允许有包含带负权值的边组成的回路。
• Floyd 算法同样适用于带权无向图，因为带权无向图可视为权值相同往返二重边的有向图。
• 也可以用单源最短路径算法来解决每对顶点之间的最短路径问题：轮流将每个顶点作为源点，并且在所有边权值均非负时，运行一次 Dijkstra 算法，其时间复杂度为 $O(|V|^2) \cdot |V| = O(|V|^3)$。

三种方法的比较

即时练习