• 【最短路必背模板】涵盖所有的「存图方式」与「最短路算法(详尽注释)」


    这是 LeetCode 上的「743. 网络延迟时间」,难度为「中等」。

    Tag : 「最短路」、「图」、「优先队列(堆)」

    有 n个网络节点,标记为1到 n。

    给你一个列表times,表示信号经过「有向边」的传递时间。

    times=(ui,vi,wi),其中 ui是源节点,vi是目标节点,wi是一个信号从源节点传递到目标节点的时间。

    现在,从某个节点 k发出一个信号。

    需要多久才能使所有节点都收到信号?

    如果不能使所有节点收到信号,返回-1。

    示例 1:

    输入:times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
    输出:2
    
    • 1
    • 2

    示例 2:

    输入:times = [[1,2,1]], n = 2, k = 1
    输出:1
    
    • 1
    • 2

    示例 3:

    输入:times = [[1,2,1]], n = 2, k = 2
    输出:-1
    
    • 1
    • 2

    提示:

    1 <= k <= n <= 100
    1 <= times.length <= 6000
    times[i].length == 3
    1 <= ui, vi <= n
    ui != vi
    0 <= wi <= 100
    所有 (ui, vi) 对都 互不相同(即,不含重复边)
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    基本分析

    为了方便,我们约定 n为点数,m为边数。

    根据题意,首先 n的数据范围只有100,m的数据范围为6000,使用「邻接表」或「邻接矩阵」来存图都可以。

    同时求的是「从 k点出发,所有点都被访问到的最短时间」,将问题转换一下其实就是求「从 k点出发,到其他点 x的最短距离的最大值」。

    存图方式

    在开始讲解最短路之前,我们先来学习三种「存图」方式。

    邻接矩阵

    这是一种使用二维矩阵来进行存图的方式。

    适用于边数较多的「稠密图」使用,当边数量接近点的数量的平方,即m≈n^2时,可定义为「稠密图」。

    // 邻接矩阵数组:w[a][b] = c 代表从 a 到 b 有权重为 c 的边
    int[][] w = new int[N][N];
    
    // 加边操作
    void add(int a, int b, int c) {
        w[a][b] = c;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    邻接表

    这也是一种在图论中十分常见的存图方式,与数组存储单链表的实现一致(头插法)。

    这种存图方式又叫「链式前向星存图」。

    如果不了解什么是链式前向星,可以查看我的另一篇博客:前向星与链式前向星

    当然也可以直接用数组+List来实现

    适用于边数较少的「稀疏图」使用,当边数量接近点的数量,即 时,可定义为「稀疏图」。

    int[] he = new int[N], e = new int[M], ne = new int[M], w = new int[M];
    int idx;
    
    void add(int a, int b, int c) {
        e[idx] = b;
        ne[idx] = he[a];
        he[a] = idx;
        w[idx] = c;
        idx++;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    首先 idx 是用来对边进行编号的,然后对存图用到的几个数组作简单解释:

    he 数组:存储是某个节点所对应的边的集合(链表)的头结点;
    e 数组:由于访问某一条边指向的节点;
    ne 数组:由于是以链表的形式进行存边,该数组就是用于找到下一条边;
    w 数组:用于记录某条边的权重为多少。
    因此当我们想要遍历所有由 a 点发出的边时,可以使用如下方式:

    for (int i = he[a]; i != -1; i = ne[i]) {
        int b = e[i], c = w[i]; // 存在由 a 指向 b 的边,权重为 c
    }
    
    • 1
    • 2
    • 3

    这是一种最简单,但是相比上述两种存图方式,使用得较少的存图方式。

    只有当我们需要确保某个操作复杂度严格为 时,才会考虑使用。

    具体的,我们建立一个类来记录有向边信息:

    class Edge {
        // 代表从 a 到 b 有一条权重为 c 的边
        int a, b, c;
        Edge(int _a, int _b, int _c) {
            a = _a; b = _b; c = _c;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    通常我们会使用 List 存起所有的边对象,并在需要遍历所有边的时候,进行遍历:

    List<Edge> es = new ArrayList<>();
    
    ...
    
    for (Edge e : es) {
        ...
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    Floyd(邻接矩阵)

    根据「基本分析」,我们可以使用复杂度为 O(n^3)的「多源汇最短路」算法, Floyd 算法进行求解,同时使用「邻接矩阵」来进行存图。

    此时计算量约为10^6,可以过。

    跑一遍 Floyd,可以得到「从任意起点出发,到达任意起点的最短距离」。

    然后从所有 w[k][x]中取max 即是「从 k点出发,到其他点 x的最短距离的最大值」。

    代码:

    class Solution {
        int N = 110, M = 6010;
        // 邻接矩阵数组:w[a][b] = c 代表从 a 到 b 有权重为 c 的边
        int[][] w = new int[N][N];
        int INF = 0x3f3f3f3f;
        int n, k;
        public int networkDelayTime(int[][] ts, int _n, int _k) {
            n = _n; k = _k;
            // 初始化邻接矩阵
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    w[i][j] = w[j][i] = i == j ? 0 : INF;
                }
            }
            // 存图
            for (int[] t : ts) {
                int u = t[0], v = t[1], c = t[2];
                w[u][v] = c;
            }
            // 最短路
            floyd();
            // 遍历答案
            int ans = 0;
            for (int i = 1; i <= n; i++) {
                ans = Math.max(ans, w[k][i]);
            }
            return ans >= INF / 2 ? -1 : ans;
        }
        void floyd() {
            // floyd 基本流程为三层循环:
            // 枚举中转点 - 枚举起点 - 枚举终点 - 松弛操作        
            for (int p = 1; p <= n; p++) {
                for (int i = 1; i <= n; i++) {
                    for (int j = 1; j <= n; j++) {
                        w[i][j] = Math.min(w[i][j], w[i][p] + w[p][j]);
                    }
                }
            }
        }
    }
    
    • 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
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40

    时间复杂度:O(n^3)
    空间复杂度:O(n^2)

    朴素 Dijkstra(邻接矩阵)

    同理,我们可以使用复杂度为 O(n^2)的「单源最短路」算法朴素 Dijkstra 算法进行求解,同时使用「邻接矩阵」来进行存图。

    根据题意,k点作为源点,跑一遍 Dijkstra 我们可以得到从源点 k 到其他点 x 的最短距离。

    再从所有最短路中取 max 即是「从 k 点出发,到其他点 x 的最短距离的最大值」。

    朴素 Dijkstra 复杂度为O(n^2),可以过。

    代码:

    class Solution {
        int N = 110, M = 6010;
        // 邻接矩阵数组:w[a][b] = c 代表从 a 到 b 有权重为 c 的边
        int[][] w = new int[N][N];
        // dist[x] = y 代表从「源点/起点」到 x 的最短距离为 y
        int[] dist = new int[N];
        // 记录哪些点已经被更新过
        boolean[] vis = new boolean[N];
        int INF = 0x3f3f3f3f;
        int n, k;
        public int networkDelayTime(int[][] ts, int _n, int _k) {
            n = _n; k = _k;
            // 初始化邻接矩阵
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    w[i][j] = w[j][i] = i == j ? 0 : INF;
                }
            }
            // 存图
            for (int[] t : ts) {
                int u = t[0], v = t[1], c = t[2];
                w[u][v] = c;
            }
            // 最短路
            dijkstra();
            // 遍历答案
            int ans = 0;
            for (int i = 1; i <= n; i++) {
                ans = Math.max(ans, dist[i]);
            }
            return ans > INF / 2 ? -1 : ans;
        }
        void dijkstra() {
            // 起始先将所有的点标记为「未更新」和「距离为正无穷」
            Arrays.fill(vis, false);
            Arrays.fill(dist, INF);
            // 只有起点最短距离为 0
            dist[k] = 0;
            // 迭代 n 次
            for (int p = 1; p <= n; p++) {
                // 每次找到「最短距离最小」且「未被更新」的点 t
                int t = -1;
                for (int i = 1; i <= n; i++) {
                    if (!vis[i] && (t == -1 || dist[i] < dist[t])) t = i;
                }
                // 标记点 t 为已更新
                vis[t] = true;
                // 用点 t 的「最小距离」更新其他点
                for (int i = 1; i <= n; i++) {
                    dist[i] = Math.min(dist[i], dist[t] + w[t][i]);
                }
            }
        }
    }
    
    • 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
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54

    时间复杂度:O(n^2)
    空间复杂度:O(n^2)

    堆优化 Dijkstra(邻接表)

    由于边数据范围不算大,我们还可以使用复杂度为 O(m*logn) 的堆优化 Dijkstra 算法进行求解。

    堆优化 Dijkstra 算法与朴素 Dijkstra 都是「单源最短路」算法。

    跑一遍堆优化 Dijkstra 算法求最短路,再从所有最短路中取 即是「从 k 点出发,到其他点 x 的最短距离的最大值」。

    此时算法复杂度为O(m*logn) ,可以过。

    代码:

    class Solution {
        int N = 110, M = 6010;
        // 邻接表
        int[] he = new int[N], e = new int[M], ne = new int[M], w = new int[M];
        // dist[x] = y 代表从「源点/起点」到 x 的最短距离为 y
        int[] dist = new int[N];
        // 记录哪些点已经被更新过
        boolean[] vis = new boolean[N];
        int n, k, idx;
        int INF = 0x3f3f3f3f;
        void add(int a, int b, int c) {
            e[idx] = b;
            ne[idx] = he[a];
            he[a] = idx;
            w[idx] = c;
            idx++;
        }
        public int networkDelayTime(int[][] ts, int _n, int _k) {
            n = _n; k = _k;
            // 初始化链表头
            Arrays.fill(he, -1);
            // 存图
            for (int[] t : ts) {
                int u = t[0], v = t[1], c = t[2];
                add(u, v, c);
            }
            // 最短路
            dijkstra();
            // 遍历答案
            int ans = 0;
            for (int i = 1; i <= n; i++) {
                ans = Math.max(ans, dist[i]);
            }
            return ans > INF / 2 ? -1 : ans;
        }
        void dijkstra() {
            // 起始先将所有的点标记为「未更新」和「距离为正无穷」
            Arrays.fill(vis, false);
            Arrays.fill(dist, INF);
            // 只有起点最短距离为 0
            dist[k] = 0;
            // 使用「优先队列」存储所有可用于更新的点
            // 以 (点编号, 到起点的距离) 进行存储,优先弹出「最短距离」较小的点
            PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[1]-b[1]);
            q.add(new int[]{k, 0});
            while (!q.isEmpty()) {
                // 每次从「优先队列」中弹出
                int[] poll = q.poll();
                int id = poll[0], step = poll[1];
                // 如果弹出的点被标记「已更新」,则跳过
                if (vis[id]) continue;
                // 标记该点「已更新」,并使用该点更新其他点的「最短距离」
                vis[id] = true;
                for (int i = he[id]; i != -1; i = ne[i]) {
                    int j = e[i];
                    if (dist[j] > dist[id] + w[i]) {
                        dist[j] = dist[id] + w[i];
                        q.add(new int[]{j, dist[j]});
                    }
                }
            }
        }
    }
    
    • 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
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63

    时间复杂度:O(m*logn + n)
    空间复杂度:O(m)

    Bellman Ford(类 & 邻接表)

    虽然题目规定了不存在「负权边」,但我们仍然可以使用可以在「负权图中求最短路」的 Bellman Ford 进行求解,当题目中对边有限制时(例如要求最多经过多少条边,可以使用迭代次数来处理)也可使用Bellman Ford来求解,该算法也是「单源最短路」算法,复杂度为 O(m * n)。

    通常为了确保 O(m * n),可以单独建一个类代表边,将所有边存入集合中,在 n 次松弛操作中直接对边集合进行遍历。

    由于本题边的数量级大于点的数量级,因此也能够继续使用「邻接表」的方式进行边的遍历,遍历所有边的复杂度的下界为 O(n),上界可以确保不超过 O(m)。

    代码:

    class Solution {
        class Edge {
            int a, b, c;
            Edge(int _a, int _b, int _c) {
                a = _a; b = _b; c = _c;
            }
        }
        int N = 110, M = 6010;
        // dist[x] = y 代表从「源点/起点」到 x 的最短距离为 y
        int[] dist = new int[N];
        int INF = 0x3f3f3f3f;
        int n, m, k;
        // 使用类进行存边
        List<Edge> es = new ArrayList<>();
        public int networkDelayTime(int[][] ts, int _n, int _k) {
            n = _n; k = _k;
            m = ts.length;
            // 存图
            for (int[] t : ts) {
                int u = t[0], v = t[1], c = t[2];
                es.add(new Edge(u, v, c));
            }
            // 最短路
            bf();
            // 遍历答案
            int ans = 0;
            for (int i = 1; i <= n; i++) {
                ans = Math.max(ans, dist[i]);
            }
            return ans > INF / 2 ? -1 : ans;
        }
        void bf() {
            // 起始先将所有的点标记为「距离为正无穷」
            Arrays.fill(dist, INF);
            // 只有起点最短距离为 0
            dist[k] = 0;
            // 迭代 n 次
            for (int p = 1; p <= n; p++) {
                int[] prev = dist.clone();
                // 每次都使用上一次迭代的结果,执行松弛操作
                for (Edge e : es) {
                    int a = e.a, b = e.b, c = e.c;
                    dist[b] = Math.min(dist[b], prev[a] + c);
                }
            }
        }
    }
    
    class Solution {
        int N = 110, M = 6010;
        // 邻接表
        int[] he = new int[N], e = new int[M], ne = new int[M], w = new int[M];
        // dist[x] = y 代表从「源点/起点」到 x 的最短距离为 y
        int[] dist = new int[N];
        int INF = 0x3f3f3f3f;
        int n, m, k, idx;
        void add(int a, int b, int c) {
            e[idx] = b;
            ne[idx] = he[a];
            he[a] = idx;
            w[idx] = c;
            idx++;
        }
        public int networkDelayTime(int[][] ts, int _n, int _k) {
            n = _n; k = _k;
            m = ts.length;
            // 初始化链表头
            Arrays.fill(he, -1);
            // 存图
            for (int[] t : ts) {
                int u = t[0], v = t[1], c = t[2];
                add(u, v, c);
            }
            // 最短路
            bf();
            // 遍历答案
            int ans = 0;
            for (int i = 1; i <= n; i++) {
                ans = Math.max(ans, dist[i]);
            }
            return ans > INF / 2 ? -1 : ans;
        }
        void bf() {
            // 起始先将所有的点标记为「距离为正无穷」
            Arrays.fill(dist, INF);
            // 只有起点最短距离为 0
            dist[k] = 0;
            // 迭代 n 次
            for (int p = 1; p <= n; p++) {
                int[] prev = dist.clone();
                // 每次都使用上一次迭代的结果,执行松弛操作
                for (int a = 1; a <= n; a++) {
                    for (int i = he[a]; i != -1; i = ne[i]) {
                        int b = e[i];
                        dist[b] = Math.min(dist[b], prev[a] + w[i]);
                    }
                }
            }
        }
    }
    
    • 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
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100

    时间复杂度:O(m * n)
    空间复杂度:O(m)

    SPFA(邻接表)

    SPFA 是对 Bellman Ford 的优化实现,可以使用队列进行优化,也可以使用栈进行优化。

    通常情况下复杂度为 O(k * m),k 一般为 4 到 5,最坏情况下仍为O(m * n) ,当数据为网格图时,复杂度会从 O(k * m) 退化为 O(n * m) 。

    代码:

    class Solution {
        int N = 110, M = 6010;
        // 邻接表
        int[] he = new int[N], e = new int[M], ne = new int[M], w = new int[M];
        // dist[x] = y 代表从「源点/起点」到 x 的最短距离为 y
        int[] dist = new int[N];
        // 记录哪一个点「已在队列」中
        boolean[] vis = new boolean[N];
        int INF = 0x3f3f3f3f;
        int n, k, idx;
        void add(int a, int b, int c) {
            e[idx] = b;
            ne[idx] = he[a];
            he[a] = idx;
            w[idx] = c;
            idx++;
        }
        public int networkDelayTime(int[][] ts, int _n, int _k) {
            n = _n; k = _k;
            // 初始化链表头
            Arrays.fill(he, -1);
            // 存图
            for (int[] t : ts) {
                int u = t[0], v = t[1], c = t[2];
                add(u, v, c);
            }
            // 最短路
            spfa();
            // 遍历答案
            int ans = 0;
            for (int i = 1; i <= n; i++) {
                ans = Math.max(ans, dist[i]);
            }
            return ans > INF / 2 ? -1 : ans;
        }
        void spfa() {
            // 起始先将所有的点标记为「未入队」和「距离为正无穷」
            Arrays.fill(vis, false);
            Arrays.fill(dist, INF);
            // 只有起点最短距离为 0
            dist[k] = 0;
            // 使用「双端队列」存储,存储的是点编号
            Deque<Integer> d = new ArrayDeque<>();
            // 将「源点/起点」进行入队,并标记「已入队」
            d.addLast(k);
            vis[k] = true;
            while (!d.isEmpty()) {
                // 每次从「双端队列」中取出,并标记「未入队」
                int poll = d.pollFirst();
                vis[poll] = false;
                // 尝试使用该点,更新其他点的最短距离
                // 如果更新的点,本身「未入队」则加入队列中,并标记「已入队」
                for (int i = he[poll]; i != -1; i = ne[i]) {
                    int j = e[i];
                    if (dist[j] > dist[poll] + w[i]) {
                        dist[j] = dist[poll] + w[i];
                        if (vis[j]) continue;
                        d.addLast(j);
                        vis[j] = true;
                    }
                }
            }
        }
    }
    
    • 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
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64

    时间复杂度:O(m * n)
    空间复杂度:O(m)

    总结

    最短路径问题还存在很多可行的解决方案,本文只罗列了一部分,我们在解题时(包括生产过程中)需要根据图数据(稠密与稀疏),以及图中边的权重是否可为负数等要求来使用对应的存图方法(邻接矩阵、邻接表、类)以及算法。

  • 相关阅读:
    (转)STR 内核做了什么
    八、混合整数线性规划问题
    Memcache概念和安装方法
    Redis代替session 实现登录流程
    自动化部署的艺术:Conda包依赖管理的终极指南
    chatgpt赋能python:Python中的随机选择:介绍和应用
    如何驾驭ChatGPT:掌控有效对话!
    【CC3200AI 实验教程4】疯壳·AI语音人脸识别(会议记录仪/人脸打卡机)-GPIO
    机器学习面试中常见问题整理
    SpringCloudGateway集成SpringDoc CORS问题
  • 原文地址:https://blog.csdn.net/weixin_45746505/article/details/128059179