【Leetcode 每日一题】743. 网络延迟时间

问题背景

有 $n$ 个网络节点，标记为 $1$ 到 $n$。
给你一个列表 $times$，表示信号经过 有向 边的传递时间。$times[i]=(u_i,v_i,w_i)$，其中 $u_i$ 是源节点，$v_i$ 是目标节点，$w_i$ 是一个信号从源节点传递到目标节点的时间。
现在，从某个节点 $K$ 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 $-1$。

数据约束

• $1\le k\le n\le 100$
• $1\le times.length\le 6000$
• $times[i].length=3$
• $1\le u_i,v_i\le n$
• $u_i!=v_i$
• $0\le w_i\le 100$
• 所有 $(u_i,v_i)$ 对都 互不相同（即，不含重复边）

解题过程

单源最短路模板题，所有权重都是正值，无脑 $Dijkstra$，时空复杂度都是 $O(n^2)$。

可以用堆来优化流程中查找最短路径的过程，在图是稀疏图的情况下（$m\ll n$）把时间复杂度优化到 $O(mlogm)$，空间复杂度为 $O(m)$，其中 $m$ 是数组 $tims$ 的长度，可以看作有向图中边的数量。但如果输入的是稠密图（$m\approx n$），这时候相对而言起主导作用的是 $m$，那么这个方法的复杂度会达到 $O(n^{2}logm)$，因为堆总是需要 $O(logm)$ 量级的时间来调整。

具体实现

朴素邻接矩阵最短路

class Solution {// 一般来说正无穷是用 Integer.MAX_VALUE 的，Dijkstra 中涉及加法会溢出private static final int INF = Integer.MAX_VALUE >>> 1;public int networkDelayTime(int[][] times, int n, int k) {int[][] graph = new int[n][n];// 初始化所有节点之间不可达for(int[] row : graph) {Arrays.fill(row, INF);}// 设置节点之间的权值for(int[] time : times) {graph[time[0] - 1][time[1] - 1] = time[2];}int max = 0;int[] dis = new int[n];Arrays.fill(dis, INF); // 初始化所有节点之间的距离为正无穷dis[k - 1] = 0; // 源节点到自身可达，使得更新过程有初始节点可选中boolean[] visited = new boolean[n]; // 初始化所有节点未访问过while(true) {// 节点编号从 0 开始，初始化为 -1 避免歧义int curIndex = -1;// 找出未访问的距源节点最近的节点for(int i = 0; i < n; i++) {if(!visited[i] && (curIndex < 0 || dis[i] < dis[curIndex])) {curIndex = i;}}// 如果所有节点都被访问过，那么最后一次更新的最短路径长度就是答案，直接返回if(curIndex < 0) {return max;}// 如果有未访问节点不可达，那么根据题目要求返回 -1if(dis[curIndex] == INF) {return -1;}// 更新这一轮的最短路径长度，Dijkstra 贪心的特点决定了这个值会越来越大max = dis[curIndex];visited[curIndex] = true; // 标记已访问过// 更新所有节点的最短路径长度for(int i = 0; i < n; i++) {dis[i] = Math.min(dis[i], dis[curIndex] + graph[curIndex][i]);} }}
}

堆优化邻接表最短路

class Solution {public int networkDelayTime(int[][] times, int n, int k) {// 初始化邻接表List<int[]>[] graph = new ArrayList[n];Arrays.setAll(graph, item -> new ArrayList<>());for(int[] time : times) {graph[time[0] - 1].add(new int[]{time[1] - 1, time[2]});}int max = 0;int remain = n; // 剩余未处理节点个数为 nint[] dis = new int[n];Arrays.fill(dis, Integer.MAX_VALUE); // 初始化所有节点之间的距离为正无穷dis[k - 1] = 0; // 源节点到自身可达，使得更新过程有初始节点可选中// 注意，堆应根据权值来调整PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((i1, i2) -> i1[1] - i2[1]);// 堆中的而元素表示到达节点和最短路径长度，也就是潜在的新路径的所有可能priorityQueue.offer(new int[]{k - 1, 0});while(!priorityQueue.isEmpty()) {int[] top = priorityQueue.poll(); // 最小堆堆顶一定是当前最近的节点int curIndex = top[0];int curDis = top[1];// 同一个节点可能会被重复记录，重复的情况不会影响结果，直接跳过if(curDis > dis[curIndex]) {continue;}// 更新这一轮的最短路径长度，Dijkstra 贪心的特点决定了这个值会越来越大max = curDis;remain--; // 当前节点处理完成，剩余未处理节点个数减少// 根据所有到达节点更新最短路径长度，增强 for 循环处理列表for(int[] row : graph[curIndex]) {int next = row[0];int newDis = curDis + row[1];if(newDis < dis[next]) {dis[next] = newDis;priorityQueue.offer(new int[]{next, newDis});}}}return remain == 0 ? max : -1; // 仍有剩余节点，说明不可达，那么根据题目要求返回 -1}
}