Dijkstra 算法-未完纪

Last update:
September 24, 2023

Translated

From: e-maxx.ru

Dijkstra 算法

给定一个包含 n 个顶点和 m 条边的有向或无向带权图，所有边的权重均非负。另给定起始顶点 s。本文讨论如何求出从 s 到其他所有顶点的最短路径长度，并输出最短路径本身。

这个问题也称为单源最短路径问题。

算法

下面介绍荷兰计算机科学家 Edsger W. Dijkstra 于1959年提出的算法。

创建数组 d[]，对每个顶点 v，用 d[v] 保存目前已知的从 s 到 v 的最短路径长度。初始时 d[s] = 0，其他顶点的距离均为无穷大。实现中使用一个足够大的数表示无穷大，且保证它大于所有可能的路径长度。

d[v] = ∞，v ≠ s

此外，维护布尔数组 u[]，记录各顶点 v 是否已被标记。初始时所有顶点均未标记：

u[v] = false

Dijkstra 算法执行 n 轮迭代。每轮从未标记顶点中选出 d[v] 最小的顶点 v：

显然，第一轮会选择起始顶点 s。

将选出的顶点 v 标记，然后从 v 进行松弛：考察所有形如 (v, to) 的边，并尝试改善每个顶点 to 的 d[to]。若当前边长为 len，松弛操作为：

d[to] = min(d[to], d[v] + len)

考察完这些边后，本轮迭代结束。经过 n 轮后，所有顶点均已标记，算法终止。我们断言，所得 d[v] 就是从 s 到各顶点 v 的最短路径长度。

如果某些顶点从 s 不可达，它们的 d[v] 会一直是无穷大。最后几轮虽会选择这些顶点，却不会完成有用工作。因此，一旦选中的顶点距离为无穷大，就可以立即结束算法。

还原最短路径

通常不仅需要最短路径长度，还需要路径本身。为了保留从 s 到任意顶点的路径还原信息，维护前驱数组 p[]。对于每个 v ≠ s，p[v] 是从 s 到 v 的最短路径中的倒数第二个顶点。这里利用了最短路径的性质：删除最短路径的最后一个顶点 v，余下到 p[v] 的路径仍然是到 p[v] 的最短路径。从 v 开始反复取当前顶点的前驱，直到到达 s，就能得到按逆序列出的路径。因此，到 v 的最短路径 P 为：

P = (s, …, p[p[p[v]]], p[p[v]], p[v], v)

构建前驱数组很简单：每次松弛成功，即从选定顶点 v 改善了到顶点 to 的距离时，将 to 的前驱更新为 v：

p[to] = v

证明

Dijkstra 算法正确性依赖的核心断言是：

顶点 v 一旦被标记，其当前距离 d[v] 就是最短距离，之后不会再改变。

使用归纳法证明。第一轮显然成立：唯一被标记的顶点是 s，d[s] = 0 确实是到 s 的最短路径长度。假设此前所有轮次、也就是所有已经标记的顶点都满足该断言，下面证明当前轮次结束后仍然成立。设当前选中的、即将标记的顶点为 v，需要证明 d[v] 等于其真实最短路径长度 l[v]。

考虑到 v 的最短路径 P。将它分为两部分：P₁ 只包含已标记顶点，至少包含起点 s；其余为 P₂，它可以包含已标记顶点，但总是从未标记顶点开始。设 P₂ 的第一个顶点为 p，P₁ 的最后一个顶点为 q。

先证明 d[p] = l[p]。这几乎显然：此前某一轮选择过 q 并从它进行了松弛。由 p 的选择方式，到 p 的最短路径就是到 q 的最短路径加上连接 q 与 p 的边，因此从 q 进行的松弛会把 d[p] 设为最短路径长度 l[p]。

由于边权非负，l[p]（刚刚已证明等于 d[p]）不会超过到 v 的最短路径长度 l[v]。而 l[v] ≤ d[v]，因为算法不可能找到比真正的最短路径还短的路径，于是得到：

d[p] = l[p] ≤ l[v] ≤ d[v]

另一方面，p 和 v 都未标记，而当前轮次选择了 v 而不是 p，因此得到：

d[p] ≥ d[v]

结合这两个不等式，有 d[p] = d[v]；再利用此前的等式，可得：

d[v] = l[v]

证毕。

实现

Dijkstra 算法执行 n 轮。每轮选择 d[v] 最小的未标记顶点 v，将其标记，并检查所有边 (v, to)，尝试改善 d[to]。

算法运行时间由以下部分组成：

在 O(n) 个未标记顶点中寻找最小 d[v] 的顶点，共 n 次。
尝试松弛，共 m 次。

最简单的实现中，每轮寻找顶点需要 O(n) 次操作，而每次松弛为 O(1)。因此，算法的渐近复杂度为：

O(n² + m)

对于稠密图，也就是 m ≈ n² 时，这个复杂度是最优的。对于 m 远小于最大边数 n² 的稀疏图，可以将复杂度降至 O(n log n + m)。算法和实现见稀疏图上的 Dijkstra 算法。

const int INF = 1000000000;
vector<vector<pair<int, int>>> adj;

void dijkstra(int s, vector<int> & d, vector<int> & p) {
    int n = adj.size();
    d.assign(n, INF);
    p.assign(n, -1);
    vector<bool> u(n, false);

    d[s] = 0;
    for (int i = 0; i < n; i++) {
        int v = -1;
        for (int j = 0; j < n; j++) {
            if (!u[j] && (v == -1 || d[j] < d[v]))
                v = j;
        }

        if (d[v] == INF)
            break;

        u[v] = true;
        for (auto edge : adj[v]) {
            int to = edge.first;
            int len = edge.second;

            if (d[v] + len < d[to]) {
                d[to] = d[v] + len;
                p[to] = v;
            }
        }
    }
}

这里使用邻接表存储图 adj：对每个顶点 v，adj[v] 保存从 v 出发的边列表，即 pair<int,int> 列表。二元组的第一项是边另一端的顶点，第二项是边权。

函数接收起始顶点 s，以及两个用作返回结果的向量。

代码首先初始化距离数组 d[]、标记数组 u[] 和前驱数组 p[]，然后执行 n 轮。每轮从所有未标记顶点中选出距离 d[v] 最小的 v。如果选中顶点的距离为无穷大，算法终止。否则标记该顶点，检查所有从它出发的边。若沿某条边可以松弛，即 d[to] 可以改善，就更新距离 d[to] 和前驱 p[to]。

执行完所有轮次后，d[] 保存到所有顶点的最短路径长度，p[] 保存所有顶点（起点 s 除外）的前驱。可以按下面的方法还原到任意顶点 t 的路径：

vector<int> restore_path(int s, int t, vector<int> const& p) {
    vector<int> path;

    for (int v = t; v != s; v = p[v])
        path.push_back(v);
    path.push_back(s);

    reverse(path.begin(), path.end());
    return path;
}