Dijkstra算法

2024-10-27

字数统计: 1.5k字 | 阅读时长: 6分

前言

寻找图中单源最短路径的经典算法，死去的考研知识点在攻击我…理论与实践重新复习一下。

Dijkstra Algorithm

Dijkstra算法是一种用于寻找图中单源最短路径的经典算法，由荷兰计算机科学家Edsger W. Dijkstra于1956年提出。该算法适用于有向图和无向图，并且要求图中的所有边权都是非负的。所谓单源最短路径，就是求某一点到其他各顶点的最短路径。

Dijkstra算法的基本思想是贪心算法。它从起点开始，逐步扩展到整个图，每次选择当前已知的最短路径进行扩展，直到找到从起点到所有其他顶点的最短路径。

算法步骤：

对于图$G$，设辅助向量$S$和$D$，其中$S$记录已求出的最短路径，$D$记录各尚未求出最短路径的顶点到起点的距离；
初状态为$S$中仅有起点$a$，$D$中记录了与$a$相邻的顶点的距离（权值），不相邻元素则为无穷大；
从$D$中找出路径最短的顶点$k$加入$S$中，更新$D$中$k$的最短距离，从$D$中移除$k$（不再参与后续计算），重复至$D$中无可用顶点。

上面的算法步骤讲述了Dijkstra算法的核心原理，考虑在编程语言下的具体实现，我们需要用合适的数据结构来构建算法的流程与上下文。

定义 $g[i][j]$ 作为图$G$，表示节点 $i$ 到节点 $j$ 这条边的边权。如果没有 $i$ 到 $j$ 的边，则 $g[i][j]=∞$。
定义 $dis[i]$ 作为集合$D$，表示起点 $a$ 到节点 $i$ 的最短路长度，一开始 $dis[a]=0$，其余 $dis[i]=∞$ 表示尚未计算出。另开辟一数组 $finished[i]$ 用于标记$D$中已被移除的元素。
对于需要不仅需要最短路径距离，且需要存储最短路径本身的情况，选用合适的数据结构存放$S$，例如动态数组等。

朴素实现（适用稠密图）

题目：现有一有向带权图，求从k节点出发到其他所有节点的最短路径和，若有节点无法到达则返回-1。

public int dijkstra(int[][] edges, int n, int k) {
    final int INF = Integer.MAX_VALUE / 2; // 防止加法溢出
    int[][] g = new int[n][n]; // 邻接矩阵 G
    for (int[] row : g) Arrays.fill(row, INF);
    for (int[] t : edges) { 
        g[t[0] - 1][t[1] - 1] = t[2]; // edges节点编号从1开始，需要映射到0开始
    }
    int maxDis = 0;
    int[] dis = new int[n]; // 集合D，本题不需要存储最短路径细节，不需要S
    Arrays.fill(dis, INF);
    dis[k - 1] = 0; // 起点
    boolean[] done = new boolean[n]; // 标记D中被移除的元素
    while (true) {
        int x = -1;
        for (int i = 0; i < n; i++) { // 寻找最小值
            if (!done[i] && (x < 0 || dis[i] < dis[x])) x = i;
        }
        if (x < 0) return maxDis; // 最后一次算出的最短路就是最大的
        if (dis[x] == INF) return -1; // 有节点无法到达
        maxDis = dis[x]; // 求出的最短路会越来越大
        done[x] = true; // 最短路长度已确定（无法变得更小）
        for (int y = 0; y < n; y++) {
            // 更新 x 的邻居的最短路
            dis[y] = Math.min(dis[y], dis[x] + g[x][y]);
        }
    }
}

时间复杂度：$O(n^2)$，空间复杂度：$O(n^2)$。

堆优化（适用稀疏图）

寻找最小值的过程可以用一个最小堆来快速完成：

一开始把 $(d i s[k], k)$ 二元组入堆。
当节点 $x$ 首次出堆时, $d i s[x]$ 就是写法一中寻找的最小最短路。
更新 $d i s[y]$ 时, 把 $(d i s[y], y)$ 二元组入堆。

注意，如果一个节点 $x$ 在出堆前，其最短路长度 $d i s[x]$ 被多次更新，那么堆中会有多个重复的 $x$ ，并且包含 $x$ 的二元组中的 $d i s[x]$ 是互不相同的（因为我们只在找到更小的最短路时才会把二元组入堆）。

所以原实现中的 done 数组可以省去, 取而代之的是用出堆的最短路值（记作 $d x$ ）与当前的 $d i s[x]$ 比较，如果 $d x>d i s[x]$ 说明 $x$ 之前出堆过，我们已经更新了 $x$ 的邻居的最短路，所以这次就不用更新了，继续外层循环。

对于同一个 $x$ ，例如先入堆一个比较大的 $\operatorname{dis}[x]=10$ ，后面又把 $\operatorname{dis}[x]$ 更新成 5 ，之后这个 5 会先出堆，然后再把 10 出堆。 10 出堆时候是没有必要去更新周围邻居的最短路的，因为 5 出堆之后，就已经把邻居的最短路更新过了，用 10 是无法把邻居的最短路变得更短的，所以直接 continue。

public int dijkstra(int[][] edges, int n, int k) {
    List<int[]>[] g = new ArrayList[n]; // 邻接表
    Arrays.setAll(g, i -> new ArrayList<>());
    for (int[] t : edges) {
        g[t[0] - 1].add(new int[]{t[1] - 1, t[2]}); // 终点, 距离
    }

    int maxDis = 0;
    int left = n; // 未确定最短路的节点个数
    int[] dis = new int[n];
    Arrays.fill(dis, Integer.MAX_VALUE);
    dis[k - 1] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
    pq.offer(new int[]{0, k - 1});
    while (!pq.isEmpty()) {
        int[] p = pq.poll();
        int dx = p[0];
        int x = p[1];
        if (dx > dis[x]) { // x 之前出堆过
            continue;
        }
        maxDis = dx; // 求出的最短路会越来越大
        left--;
        for (int[] e : g[x]) {
            int y = e[0];
            int newDis = dx + e[1];
            if (newDis < dis[y]) {
                dis[y] = newDis; // 更新 x 的邻居的最短路
                pq.offer(new int[]{newDis, y});
            }
        }
    }
    return left == 0 ? maxDis : -1;
}

参考文献

[1] https://leetcode.cn/problems/network-delay-time/solutions/2668220/liang-chong-dijkstra-xie-fa-fu-ti-dan-py-ooe8/

后记

首发于 silencezheng.top，转载请注明出处。