迪杰斯特拉算法(Dijkstra)

摘要: 迪杰斯特拉算法原理与代码模板

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

迪杰斯特拉（Edsger Wybe Dijkstra）在一个充满科学气息的家庭背景中长大，父亲是化学家、母亲是数学家。他最早希望在联合国从事法律方面的工作，不过后来还是选择了研究数学和物理。1948 年进入 Leyden 大学并转为计算机，此后在计算机领域取得非常多的成果，是计算机的先驱之一。下面是一些比较重要的成果：

• 提出”goto有害论”;
• 提出信号量和原语;
• 解决”哲学家聚餐”问题;
• 最短路径算法；
• 银行家算法;
• 第一个 Algol 60 编译器的设计者和实现者;
• THE 操作系统的设计者和开发者;

《编程的修炼》是他写的一本书，至今仍然在出版，最新版在微信读书上可以看：编程的修炼 。当然本书非常形式化并且很抽象，比较难读。

本文我们串讲一下带权图最短路径的 Dijkstra 算法，包括其思想、算法设计、正确性证明、代码模板。

单源最短路径问题

给定一个有向带权图 $G = (V, E)$，$V$ 是点集，$E$ 是边集。$|V| = n, |E| = m$，编号为 $[0, N-1]$。

$(x, y, z)$ 表示一条从 $x$ 出发到 $y$ 的有向边，边权为 $z$。

指定 $V$ 中的一个点 $S=0$ 作为源点，要计算从源点到所有节点的最短路径长度。

也就是求数组 dist，其中 dist[i] 表示从源点 $S=0$ 到节点 $i$ 的最短路径长度。

Dijkstra 思想

迪杰斯特拉（Dijkstra）提出按照各个顶点与源点之间路径长度的递增次序，生成源点到各个顶点的最短路径的方法。也就是先求出长度最短的一条路径，然后参照该路径求出长度次短的一条路径，以此类推，直到从源点到其他各个顶点的最短路径全部求出。

思想很好理解，但要形成具体的算法，还需要进行相应的设计。

注意 Dijkstra 算法要求每条边的权是非负数，原因在后面的正确性证明中可以看出来。

算法设计（贪心）

令源点为 $u$，顶点集合 $V$ 分为两部分 $S$ 和 $V - S$，其中 $S$ 中的顶点到源点的最短路径的长度已经确定。而集合 $V - S$ 中的顶点到源点的最短路径长度尚未确定。

Dijkstra 算法在每一轮从 $V - S$ 中选出一些点放入 $S$ 中，从 $V - S$ 中选择点的策略是贪心的，贪心策略具体如下：

从源点出发的所有路径中，会有一些路径只经过 $S$ 中的点到达 $V-S$ 中的点，称这种路径为特殊路径，从这些特殊路径中找到长度最短的那个，然后将最短的特殊路径对应在 $V - S$ 中的点加入到 $S$ 中。

基于上面这个贪心策略，我们给出算法流程。首先定义图的数据结构以及算法所需的变量：

g: 邻接表, g[u] 为所有从 u 出发的边 uv 对应的节点 v 的集合
d: 维护最短路径，d[u] 为从源点到 u 在当前迭代轮次的最短路径，d[u] = -1 表示该点尚未访问到
   初始时 d[start] = 0，其余为 -1
visited: 记录是否找到最短路径，visited[u] = 1 表示已经找到从 u 到源点的最短路径，为 0 表示没有找到
         初始时只有 visited[start] = 1

以下 (1)(2) 的流程循环 N - 1 次:

• (1) 从尚未找到最短路径长度，也就是满足 !visited[u] 的节点中，找到这些节点中到源点距离最短的节点，节点编号为 min_idx，最短路径为 min_val。
• (2) 根据这个节点 min_idx 的最短路大小 min_val，更新 min_idx 的各个后继节点的路径长度。

实现上面的算法最重要的一步是从当前迭代轮次中 $V - S$ 中的节点中找到距离源点长度最短的那个。根据情况有两种实现方式，一种是用数组 d 维护 $V - S$，每次每次都遍历一次 d 找到最小的；另一种是使用最小堆维护 $V - S$，这样每轮迭代中，堆头自然就是要找的最小值。

实现方式1：数组

时间复杂度：$O(E + V^2)$

vector<int> dijkstra_array(vector<vector<vector<int> > >& g, int start, int N)
{
    // dijkstra 数组实现 O(E + V^2)
    // 不能有负权

    // 存放 start 到各个点的最短路径
    vector<int> d(N + 1, -1);
    d[start] = 0;
    // 记录是否找到 start 到该点的最短路径
    vector<bool> visited(N + 1, false);
    visited[start] = true;

    // 初始化 start 到各个点的距离
    for(vector<int> son: g[start])
        d[son[0]] = son[1];

    for(int cnt = 1; cnt <= N - 1; ++cnt)
    {
        int min_val = INT_MAX / 2, min_idx = 0;
        // 遍历所有节点，找到离 start 最近的节点
        for(int i = 1; i <= N; ++i)
        {
            if(d[i] != -1 && !visited[i] && d[i] < min_val)
            {
                min_idx = i;
                min_val = d[i];
            }
        }

        // 标记离 start 最近距离节点已经找到
        visited[min_idx] = true;

        // 根据刚刚找到的距离 start 最短的节点，
        // 通过该节点更新 start 与其它节点的距离
        for(vector<int> son: g[min_idx])
        {
            if(d[son[0]] != -1) // 之前路径与当前更新路径的最小值
                d[son[0]] = min(d[son[0]], min_val + son[1]);
            else // 该节点第一次访问，直接更新
                d[son[0]] = min_val + son[1];
        }
    }
    return d;
}

实现方式2：堆

vector<int> dijkstra_heap(vector<vector<vector<int> > >& g, int start, int N)
{
    // dijkstra 堆实现，有延迟删除策略 O(E\log E)
    // 不能有负权

    // 存放 start 到各个点的最短路径
    vector<int> d(N + 1, INT_MAX / 2);
    d[start] = 0;

    // 队列元素 (节点编号，到 start 的距离)
    priority_queue<vector<int>, vector<vector<int> >, Cmp> pq; 
    pq.push({start, 0});
    while(!pq.empty())
    {
        vector<int> cur = pq.top();
        pq.pop();
        if(d[cur[0]] < cur[1]) 
            continue;
        for(vector<int> son: g[cur[0]])
        {
            if(d[son[0]] <= d[cur[0]] + son[1]) 
                continue;
            d[son[0]] = d[cur[0]] + son[1];
            pq.push({son[0], d[son[0]]});
        }
    }
    return d;
}

struct Cmp
{
    bool operator() (const vector<int>& item1, const vector<int>& item2)
    {
        return item1[1] > item2[1]; // 最小堆
    }
};

延迟删除与时间复杂度

在实现 Dijkstra 以及某些图中节点可能多次被访问的优先级队列 BFS （例如 AStar）中时，一个很好的技巧是使用“延迟删除”。

以 Dijkstra 算法为例，主循环从优先级队列中提取下一个要处理的节点 $u$，并对其所有相邻节点 $v$ 进行分析，根据情况可能改变 $v$ 的最小路径代价。此时如果 $v$ 已经在优先级队列中，相当于要将 $v$ 的优先级变小（$v$ 距离源点的距离发现了更小值）。

改变堆中已有元素的优先级实现起来很繁琐，延迟删除的做法是不对堆中已有节点做修改，而将该节点的“新副本”(及其新的更小的优先级，即到源点的距离)添加到优先级队列中。由于新副本到源点距离较短，将在原始副本之前弹出，因此将会更早地处理新副本。

这种“延迟删除”的问题是，具有较高的距离值的原始副本，最终也是要从优先级队列中弹出的，于是 Dijkstra 主循环在从优先级队列中弹出节点时，必须做的第一件事就是检查该节点是否已经被弹出过。如果弹出过，则跳过对该节点的操作，相当于该节点在此时从堆中被删除。

由于延迟删除的策略，一个节点是有可能重复压入堆中的，因此堆中元素个数就会比 $V$ 要多，最坏情况下堆中有 $O(E)$ 个元素，这样在弹出时的时间复杂度就是 $O(\log E)$，如果使用索引堆等方式，可以支持直接更改指定节点的优先级，那么就可以保持堆中元素个数为 $O(V)$，这样在弹出时的时间复杂度就是 $O(\log V)$ 了。

因此这里使用延时删除的时间复杂度为 $O(E\log E)$（若用索引堆等方式保持堆中没有标记删除的节点，则时间复杂度为 $O(E\log V)$）。

正确性证明

贪心选择性质

Dijkstra 算法中的贪心策略是从集合 $V-S$ 中选择具有最短路径的顶点 min_idx，从而得到从源点 start 到 min_idx 的最短路径长度为 d[min_idx]。

要证明 min_idx 是最优的选择，也就是证明从 start 到 min_idx 没有更短的其他路径。

假设存在一条从源点 start 到 min_idx 更短的路径。设该路径初次走出 $S$ 之外到达的顶点为 $x \in V - S$，然后进入 $S$ 中的节点、离开 $S$ 中的节点若干次，最后离开 $S$ 到达 min_idx。

这条路径上，记：

• d(start, x) 为从源点 start 到 x 的路径长度
• d(x, min_idx) 为从点 x 到 min_idx 的路径长度

于是有：

d[x] <= d(start, x) 
d(start, x) + d(x, min_idx) < d[min_idx]

由于边权的非负性，d(x, min_idx) >= 0，从而 d[x] < d[min_idx]，与之前的算法流程矛盾。因此 d[min_idx] 是从 start 到 min_idx 的最短路径长度。

最优子结构性质

前面我们只证明了在某一轮次时，min_idx 是 $V-S$ 中具有到源点最短距离的节点，但是该点在该轮次对应的距离 d[min_idx] 是否是全局的最短距离还不知道。

最优子结构性质要说明的是将 d[min_idx] 从 $V-S$ 插入到 $S$ 后，就不会改变了。要证明这一点，我们考察添加 min_idx 到 $S$ 后，d[min_idx] 的值所引起的变化即可。

我们记 $S$ 增加 min_idx 后变为 $S’$。添加 min_idx 之后，可能出现一条到 $V-S$ 中某个顶点 $v$ 的新的特殊路径。

如果这条路径是先经过 $S$ 到达 min_idx，然后从 min_idx 经过一条边直接到达 $v$，则这条路径的长度是 d[min_idx] + cost[min_idx][v]。此时如果 d[min_idx] + cost[min_idx][v] < d[v]，则算法中用 d[min_idx] + cost[min_idx][v] 作为 d[v] 的新值。

如果这条新路径经过 $S$ 到达 min_idx 之后，不是从一条边直接到达 $v$，而是先回到 $S$ 中的某个点 $x$，最后才到达 $v$，那么由于 $x\in S$，因此 $x$ 比 min_idx 先加入 $S$，也就是从源 start 到 $x$ 的路径长度比从源点到 min_idx，再从 min_idx 到 $x$ 的路径长度小。于是当前 d[v] 的值小于从源点 start 经过 min_idx、$x$ 到 $v$ 的路径长度。

因此，无论算法中 d[min_idx] 的值是否有变化，它总是从当前顶点集 $S$ 到顶点 min_idx 的最短路径长度。

---