LeetCode743、网络延迟时间

题目描述

题目链接：https://leetcode.cn/problems/network-delay-time/description/

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

示例 1： OiEqbXXdKoEtxCx3gd0cqd3knud.png

输入：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 <= u(i), v(i) <= n u(i) != v(i) 0 <= w(i) <= 100 所有 (u(i), v(i)) 对都 互不相同（即，不含重复边）

题目解析

好的，没问题！我是你的专属算法老师，AlgoMooc。今天我们不讲枯燥的公式，我们来聊一个“传话”的故事，把这个看似复杂的题目彻底搞懂。

---

### 题目在说什么

想象一下，你是一个网络管理员，有 n 个网络节点（比如路由器），它们之间通过一些有方向的线路连接。每条线路 (u, v, w) 告诉你：从节点 u 发信号到节点 v，需要花费 w 毫秒。

现在，领导让你从某个特定的节点 k 发出一条指令。你的任务是：计算一下，最快需要多久，才能让所有节点都收到这个指令？

如果有些节点根本连不上（比如线路断了），那任务就不可能完成，你就得返回 -1。

举个例子：

• 节点：1, 2, 3, 4
• 线路：[2,1,1] (2→1 要1毫秒)，[2,3,1] (2→3 要1毫秒)，[3,4,1] (3→4 要1毫秒)
• 起点：节点 2

信号从2出发：

• 1毫秒后，节点1和节点3都收到了。
• 节点3收到后，它马上转发给节点4，又过了1毫秒，节点4收到。
• 所以，所有节点都收到信号，是在第2毫秒（节点4收到的时候）。

因此，答案是 2。

---

### 思路是怎么来的

这个问题，本质上就是一个 “单源最短路径” 问题。什么意思呢？就是从一个起点出发，找到去往其他所有节点的最短路径。而题目问的“多久”，其实就是这些最短路径里，最长的那一条。

生活化比喻：快递小哥的烦恼

想象你是一个快递小哥，要从公司（节点K）出发，给全城（所有节点）的客户送包裹。每条路（有向边）都有不同的通行时间（权重w）。

你的目标是：让最后一个客户收到包裹的时间，尽可能早。 因为最后一个客户收到包裹的时间，就是整个派送任务的完成时间。

你怎么规划路线呢？你肯定不会走远路，对吧？你会每次都选择去往下一个“最快能到达”的、还没送过的客户那里。这就是 Dijkstra（迪杰斯特拉）算法 的核心思想。

Dijkstra 算法的核心逻辑：

1. 先记个账本：用一个表格 dist，记录从公司到每个客户“目前已知的最快时间”。一开始，除了公司（时间为0），其他客户都记成“无穷大”（表示还不知道怎么去）。 2. 从公司出发：公司就是第一个“已确定最快时间”的点。 3. 贪心选择：从“还没确定最快时间”的客户里，挑一个“目前已知时间”最短的。这个时间，就是从他到公司的最短时间了，不会再变了。为什么？因为所有路的时间都是正数（题目里w>=0），你不可能绕路反而更快。 4. 更新邻居：找到这个客户后，看看从他那里出发，能不能让他的邻居们更快收到包裹。如果能，就更新邻居们的“账本”。 5. 重复：重复步骤3和4，直到所有客户的最短时间都确定了。

回到题目：我们只需要用 Dijkstra 算法，算出从节点K到所有其他节点的最短时间，然后找出这些时间里的最大值。如果这个最大值是“无穷大”，就说明有节点到不了，返回 -1。

---

### 代码逐步拆解

现在，我们对照着代码，一步步看它是怎么实现这个“快递小哥”算法的。

import java.util.*;

class Solution {
    // 定义一个非常大的数，代表“无穷大”，表示节点不可达
    static final int INF = 100000; 

    public int networkDelayTime(int[][] times, int n, int k) {
        // ----- 第一步：建立“地图”（邻接表） -----
        // 我们用一种叫“邻接表”的结构来存储地图。
        // 它的样子是：{节点1: [ (邻居节点, 时间), ... ], 节点2: [ ... ], ...}
        Map<Integer, List<int[]>> neighbor_dic = new HashMap<>();
        
        // 初始化地图，给每个节点都准备一个空列表，用来放它的邻居
        for (int i = 1; i <= n; i++) {
            neighbor_dic.put(i, new ArrayList<>());
        }
        
        // 遍历题目给的线路列表，把每条线路信息填进地图
        for (int[] time : times) {
            int a = time[0], b = time[1], w = time[2];
            // 在节点a的邻居列表里，添加一个记录：(邻居b, 时间w)
            neighbor_dic.get(a).add(new int[]{b, w});
        }

        // ----- 第二步：准备“账本”（dist数组）和“优先队列” -----
        // dist[i] 表示从起点k到节点i的“目前已知最短时间”
        int[] dist = new int[n + 1]; 
        Arrays.fill(dist, INF); // 一开始，除了起点，其他都是“无穷大”
        dist[k] = 0; // 起点到自己的时间是0

        // 优先队列（最小堆）是Dijkstra算法的核心工具。
        // 它就像一个“待办事项列表”，但会自动排序，把“当前时间最短”的节点排在最前面。
        // 队列里放的是 [当前时间, 节点编号]
        PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        heap.offer(new int[]{0, k}); // 从起点开始，时间是0

        // ----- 第三步：开始“贪心”遍历（核心循环） -----
        while (!heap.isEmpty()) {
            // 从优先队列里取出“当前时间最短”的节点
            int[] cur = heap.poll();
            int cur_time = cur[0], cur_node = cur[1];

            // 小优化：如果这个节点已经被更短的时间处理过了，就跳过。