侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【图, 单源最短路径, Dijkstra算法, Bellman-Ford算法, 动态规划】网络延迟时间

GabrielxD
2022-05-31 / 0 评论 / 0 点赞 / 48 阅读 / 2,281 字 / 正在检测是否收录...

题目

743. 网络延迟时间


n 个网络节点,标记为 1n

给你一个列表 times,表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi),其中 ui 是源节点,vi 是目标节点, wi 是一个信号从源节点传递到目标节点的时间。

现在,从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号?如果不能使所有节点收到信号,返回 -1

示例 1:

image-20220531014358609

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

示例 2:

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

示例 3:

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

提示:

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

解题

前置知识

  • 单源最短路径:指的是在加权图中,给定一个起点,求出它分别到其他顶点的**「最短路径」**。
  • Dijkstra算法:

将所有节点分成两类:

  • 已确定从起点到当前点的最短路长度的节点(「未确定节点」)。
  • 未确定从起点到当前点的最短路长度的节点(「已确定节点」)。

每次从「未确定节点」中取一个与起点距离最短的点,将它归类为「已确定节点」,并用它「更新」从起点到其他所有「未确定节点」的距离,直到所有点都被归类为「已确定节点」。

用节点 A「更新」节点 B 的意思是,用 起点到节点 A 的最短路长度 加上 从节点 A 到节点 B 的边的长度,去比较 起点到节点 B 的最短路长度,如果前者小于后者,就用前者更新后者。这种操作也被叫做「松弛」。

这里暗含的信息是:每次选择「未确定节点」时,起点到它的最短路径的长度可以被确定。

可以这样理解,因为我们已经用了每一个「已确定节点」更新过了当前节点,无需再次更新(因为一个点不能多次到达)。而当前节点已经是所有「未确定节点」中与起点距离最短的点,不可能被其它「未确定节点」更新。所以当前节点可以被归类为「已确定节点」。

方法一:Dijkstra算法 邻接矩阵

思路

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

把表示路径无穷大的 INF 初始化为 最大可能权值max(wi)最多可能边数max(len(times))最大可能权值 max(w_i) * 最多可能边数 max(len(times))

代码中将节点编号减小了 11,从而使节点编号位于 [0,n1][0,n-1] 范围,故下文中的 k 代表代码中的 k-1

使用题目给出的数组 times 构建一个邻接矩阵(graph),方便后面查找顶点关系与边权值。
因为边的权值有可能为 00<=wi<=1000 <= w_i <= 100),所以应该把邻接矩阵中元素全部初始化为 INF 再开始构建邻接矩阵。

初始化表示最短距离的数组(dist),其中 dist[i] 表示从节点 k 到节点 i 的最短路值。

初始化访问数组(visited),其中 visited[i] 表示节点 i 是否被访问过。

循环 n 次:

  • 每次找到「从k开始最短距离最小」且「未被访问过」的点 min
  • 标记 min 顶点为已访问。
  • 用顶点 min 的「最小距离」更新其他顶点。

完成循环后遍历 dist 数组,从中取出「最短距离的最大值」(ans),如果 ans==INF 说明不能使所有节点收到信号(从图的角度来说其实是该图的连通分量大于 1),返回 -1,否则直接返回 ans

代码

朴素 Dijkstra 算法 + 邻接矩阵

class Solution {
    private static final int INF = 100 * 6000;

    public int networkDelayTime(int[][] times, int n, int k) {
        // 邻接矩阵数组: graph[x][y]=weight 表示从x到y有权重为weight的边
        int[][] graph = new int[n][n];
        // 因为边的权值有可能为0, 初始化邻接矩阵为无穷大
        for (int[] row : graph) Arrays.fill(row, INF);
        // 构造邻接矩阵
        for (int[] time : times) {
            graph[time[0] - 1][time[1] - 1] = time[2];
        }
        // dist[i]=weight 表示从起点k到i的最短距离为weight
        int[] dist = new int[n];
        // 初始化所有顶点的“最短距离”为正无穷
        Arrays.fill(dist, INF);
        // 把起点相于自己的最短距离置为0
        dist[k - 1] = 0;
        // 初始化访问数组 visited[i]==true 表示顶点i已经被访问过 反之
        boolean[] visited = new boolean[n];
        // 迭代m次
        for (int i = 0; i < n; i++) {
            int min = -1;
            // 找到「“最短距离”最小」且「未被访问过」的顶点 min
            for (int j = 0; j < n; j++) {
                if (visited[j]) continue;
                if (min == -1 || dist[j] < dist[min]) min = j;
            }
            // 标记顶点 min 为已访问
            visited[min] = true;
            // 用顶点 min 的“最短距离”更新其他顶点
            for (int j = 0; j < n; j++) {
                dist[j] = Math.min(dist[j], dist[min] + graph[min][j]);
            }
        }
        int ans = 0;
        // 遍历“最短距离”数组 从中取出最大的
        for (int d : dist) {
            ans = Math.max(ans, d);
        }
        return ans == INF ? -1 : ans;
    }
}

方法二:Bellman-Ford算法 动态规划 类存图

思路

既然是求单源最短路问题,也可以使用 Bellman-Ford 算法。

代码

class Solution {
    private static final int INF = Integer.MAX_VALUE >> 1;
    
    public int networkDelayTime(int[][] times, int n, int k) {
        List<Edge> edges = new ArrayList<>();
        for (int[] time : times) {
            edges.add(new Edge(time[0] - 1, time[1] - 1, time[2]));
        }
        int[][] dp = new int[n][n];
        for (int[] row : dp) Arrays.fill(row, INF);
        for (int i = 0; i < n; i++) dp[i][k - 1] = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (Edge edge : edges) {
                    if (edge.dest == j) {
                        dp[i][j] = Math.min(dp[i][j], dp[i - 1][edge.src] + edge.weight);
                    }
                }
            }
        }
        int ans = 0;
        for (int d : dp[n - 1]) {
            ans = Math.max(ans, d);
        }
        return ans == INF ? -1 : ans;
    }

    static class Edge {
        public int src;
        public int dest;
        public int weight;

        public Edge(int src, int dest, int weight) {
            this.src = src;
            this.dest = dest;
            this.weight = weight;
        }
    }
}

优化

仔细观察题目已经给了现成的图,只不过是用数组表示的:

  • times[e][0] 表示 e.src
  • times[e][1] 表示 e.dest
  • times[e][2] 表示 e.weight
class Solution {
    private static final int INF = Integer.MAX_VALUE >> 1;
    
    public int networkDelayTime(int[][] times, int n, int k) {
        int[][] dp = new int[n][n];
        for (int[] row : dp) Arrays.fill(row, INF);
        for (int i = 0; i < n; i++) dp[i][k - 1] = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int[] edge : times) {
                    if (edge[1] - 1 != j) continue;
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][edge[0] - 1] + edge[2]);
                }
            }
        }
        int ans = 0;
        for (int d : dp[n - 1]) {
            ans = Math.max(ans, d);
        }
        return ans == INF ? -1 : ans;
    }
}

优化:滚动数组

因为动态规划中只需要用到当前行(dp[i])和上一行(dp[i-1]),所以可以使用滚动数组进行优化,具体来说:
只用维护一个 dist 数组表示「从起始顶点最多经过 xx 条边到所有顶点的最短路」,每次循环拷贝一份 distprev 表示「从起始顶点最多经过 x1x-1 条边到所有顶点的最短路」。

class Solution {
    private static final int INF = Integer.MAX_VALUE >> 1;
    
    public int networkDelayTime(int[][] times, int n, int k) {
        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        dist[k - 1] = 0;
        for (int i = 1; i < n; i++) {
            int[] prev = dist.clone();
            for (int dest = 0; dest < n; dest++) {
                for (int[] edge : times) {
                    if (edge[1] - 1 != dest) continue;
                    dist[dest] = Math.min(dist[dest], dist[edge[0] - 1] + edge[2]);
                }
            }
        }
        int ans = 0;
        for (int d : dist) {
            ans = Math.max(ans, d);
        }
        return ans == INF ? -1 : ans;
    }
}

优化:剪枝

如果在某次循环中没有最短路径被更新,就说明所有最短路径都被求出来了,接下来的可能路径也不会更短,就可以直接退出外循环。

class Solution {
    private static final int INF = Integer.MAX_VALUE >> 1;
    
    public int networkDelayTime(int[][] times, int n, int k) {
        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        dist[k - 1] = 0;
        for (int i = 1; i < n; i++) {
            boolean hasShorterPath = false;
            int[] prev = dist.clone();
            for (int[] edge : times) {
                int src = edge[0] - 1;
                int dest = edge[1] - 1;
                int weight = edge[2];
                if (dist[src] + weight < dist[dest]) {
                    dist[dest] = dist[src] + weight;
                    hasShorterPath = true;
                }
            }
            if (!hasShorterPath) break;
        }
        int ans = 0;
        for (int d : dist) {
            ans = Math.max(ans, d);
        }
        return ans == INF ? -1 : ans;
    }
}
0

评论区