【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;
            }
            // 如果有未访问节点不可达，那么根据题目要求返回 -1
            if(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; // 剩余未处理节点个数为 n
        int[] 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
    }
}