LeetCode 743. 网络延迟时间

2021-12-08 HGNULB 约 13 分钟

文章信息 9 个分类 6 个标签

分类

题目描述

✅ 743. 网络延迟时间

题意分析

有 n 个编号从 1 到 n 的节点，times[i] = [u, v, w] 表示信号从 u 传到 v 需要 w 的时间。从节点 k 同时向外发出信号，问所有节点都收到信号需要多久；若存在收不到的节点，返回 -1。

「同时发出」这四个字要读透。信号沿所有路径并行传播，某个节点收到信号的时刻，就是它从 k 出发的最短路径长度——先到的那份信号定下时刻，后到的没有意义。而「所有节点都收到」意味着要等最慢的那一个，所以答案是所有节点最短路的最大值。这两句合起来把题目翻译成了一个完全标准的问题：单源最短路，再取全体最大。

times[i] = [u, v, w] 的三元组是有向的，信号只能从 u 流向 v。这一点在建图时最容易疏忽——反向加边会得到一张完全不同的图，而且往往还能跑出答案，只是答案是错的。

权重 w 的取值范围是 $[0, 100]$，非负。这是全题最关键的算法信号：非负边权是贪心式最短路算法成立的前提。如果题目允许负权，就必须换成基于松弛轮次的算法。

规模上，节点数 $n \le 100$，边数最多 6000。这个规模其实很小，$O(n^3)$ 的全源最短路也能过，但边数远小于 $n^2$ 的稀疏图更适合用堆优化的写法，而且这个写法在 $n$ 放大到 $10^5$ 时依然成立，是面试中该给出的版本。

边界有三处：起点 k 自己的时刻是 0，必须计入最大值的比较（当 n = 1 时答案就是 0）；节点编号从 1 开始，数组要开 n + 1 长以免下标错位；存在不可达节点时不能返回一个巨大的数，必须识别出来返回 -1。

解法：Dijkstra 最短路

核心思路

先看朴素做法：从 k 出发做深度优先搜索，枚举所有路径，对每个节点记录见过的最小总权。图里有环时路径数量爆炸，同一个节点会被反复以更差的路径重新访问，复杂度不可控。

瓶颈在于「不知道什么时候一个节点的答案已经定死了」，所以每条路径都得试。而边权非负给出了一个决定性的性质：沿着一条路径继续走下去，总长度只会变大不会变小。由此可以推出一个贪心结论——在所有「尚未确定」的节点中，当前估计距离最小的那一个，它的估计值已经就是最终答案。理由是任何想要改进它的新路径，都必须先经过另一个尚未确定的节点，而那个节点的距离不小于它，再叠加一段非负权，只会更长。

这个结论把问题从「枚举路径」变成了「每轮定死一个节点」：反复取出未确定节点里距离最小的，宣布它定稿，然后用它去松弛（尝试缩短）它的出边邻居。每个节点定稿一次，总共 n 轮，就得到了全部最短路。

「取出最小值」这个操作用小顶堆实现，就是堆优化版本。堆里存的是 (距离, 节点) 二元组，按距离排序。

需要维护的核心不变量是：dist[v] 始终等于「只经过已定稿节点作为中转」时，从 k 到 v 的最短长度；而每次从堆顶弹出的、且未过期的节点，其 dist 值就是它真正的最短路。前半句由每次定稿后立即松弛全部出边来保证，后半句由上面的贪心论证保证。

实现上有个细节：一个节点的距离可能被松弛多次，于是堆里会残留同一节点的多个旧记录。与其去堆中删除，不如让它们留着，弹出时用 d > dist[node] 判断——若弹出的距离比当前记录的距离大，说明这是一条被更优路径淘汰过的过期记录，直接跳过即可。这种「懒删除」是堆优化 Dijkstra 的标准写法，比手写可减堆简单得多，也是面试时该选的实现。

最后一步是收尾：扫一遍 dist，若还有节点保持初始的无穷大，说明它压根不在 k 的可达集合里，返回 -1；否则取最大值作为答案。

解题步骤

建有向带权邻接表：graph[u] 里存 (v, w)。用邻接表而不是邻接矩阵，是因为边数 6000 远小于 $100^2$，而且邻接表让「遍历某点的出边」这一操作正比于出度而非 n。只加 u → v 一条边，不能顺手加反向边。

dist 数组开 n + 1 长，全部填成无穷大，再置 dist[k] = 0。开 n + 1 是为了让编号 1 到 n 直接当下标用，省掉全篇的 ±1 换算。无穷大既是「尚未找到任何路径」的初值，也是收尾阶段识别不可达的标志，所以不能用 0 或 -1 代替。Java 里用 Integer.MAX_VALUE，Go 里用 1 << 60，两者都远大于任何可能的真实路径长（最多 $100 \times 100$）。

把 (0, k) 压入小顶堆，作为唯一的搜索起点。

循环弹出堆顶 (d, node)，先判 d > dist[node] 则 continue。这一句是懒删除的判定，跳过的是被后来更优路径淘汰的过期记录。缺了它虽然不影响正确性（旧记录松弛不出更小的值），但会白白多做一轮出边遍历。

遍历 node 的每条出边 (next, w)，若 dist[node] + w < dist[next] 则更新 dist[next] 并把新的 (dist[next], next) 入堆。入堆的必须是更新后的新距离，让它在堆里按新值排序；只有真正缩短了才入堆，否则堆会被无效记录撑爆。

循环直到堆空。堆空意味着再没有可以扩展的节点，k 的可达集合已经全部定稿。

收尾扫描 1 到 n：遇到仍是无穷大的立即返回 -1；否则用 max 累计最大值返回。累计的起点取 0 而不是负数，这样 n = 1 时（只有起点自己、dist[k] = 0）能正确返回 0。

以 times = [[2,1,1],[2,3,1],[3,4,1]]、n = 4、k = 2 走一遍。

建图后 graph[2] = [(1,1), (3,1)]，graph[3] = [(4,1)]，节点 1 和 4 没有出边。dist = [_, ∞, 0, ∞, ∞]（下标 0 不用），堆里是 {(0,2)}。

第一轮：弹出 (0, 2)，0 == dist[2] 不过期。松弛出边：dist[2] + 1 = 1 < ∞，于是 dist[1] = 1 并压入 (1,1)；同理 dist[3] = 1 并压入 (1,3)。此时 dist = [_, 1, 0, 1, ∞]，堆里是 {(1,1), (1,3)}。

第二轮：弹出距离最小的记录之一，设为 (1, 1)，不过期。节点 1 没有出边，什么都不做。堆里剩 {(1,3)}。

第三轮：弹出 (1, 3)，不过期。松弛 3 → 4：dist[3] + 1 = 2 < ∞，于是 dist[4] = 2 并压入 (2,4)。堆里是 {(2,4)}。

第四轮：弹出 (2, 4)，不过期，节点 4 无出边。堆空，循环结束。

收尾扫描 dist[1..4] = [1, 0, 1, 2]，无穷大不存在，最大值为 2，返回 2。

再看不可达的情形：同样的 times，但取 k = 1。节点 1 没有出边，第一轮弹出 (0, 1) 后堆立刻空掉，dist = [_, 0, ∞, ∞, ∞]。收尾扫描到 dist[2] == ∞，返回 -1。

若建图时把方向写反（写成 graph[t[1]].add(t[0], t[2])），k = 2 这组的边会变成 1 → 2、3 → 2、4 → 3，从 2 出发一条边都走不出去，dist[1]、dist[3]、dist[4] 全是无穷大，返回 -1 而不是 2。方向搞反时代码不会报任何错，只会静默给出错误答案。

代码实现

class Solution {
    // 用优先队列维护当前可扩展的最小距离节点。
    public int networkDelayTime(int[][] times, int n, int k) {
        List<int[]>[] graph = new List[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] t : times) {
            graph[t[0]].add(new int[] {t[1], t[2]});
        }

        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[] {0, k});

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int d = cur[0];
            int node = cur[1];

            if (d > dist[node]) {
                continue;
            }

            for (int[] edge : graph[node]) {
                int next = edge[0];
                int w = edge[1];
                if (dist[node] + w < dist[next]) {
                    dist[next] = dist[node] + w;
                    pq.offer(new int[] {dist[next], next});
                }
            }
        }

        int answer = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) {
                return -1;
            }
            answer = Math.max(answer, dist[i]);
        }

        return answer;
    }
}

type Edge struct {
    // 用优先队列维护当前可扩展的最小距离节点。
    to   int
    cost int
}

type Item struct {
    node int
    dist int
}

type MinHeap []Item

func (h MinHeap) Len() int            { return len(h) }
func (h MinHeap) Less(i, j int) bool  { return h[i].dist < h[j].dist }
func (h MinHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x any) { *h = append(*h, x.(Item)) }
func (h *MinHeap) Pop() any {
    old := *h
    n := len(old)
    item := old[n-1]
    *h = old[:n-1]
    return item
}

func networkDelayTime(times [][]int, n int, k int) int {
    graph := make([][]Edge, n+1)
    for _, t := range times {
        graph[t[0]] = append(graph[t[0]], Edge{to: t[1], cost: t[2]})
    }

    const inf = int(1 << 60)
    dist := make([]int, n+1)
    for i := 1; i <= n; i++ {
        dist[i] = inf
    }
    dist[k] = 0

    h := &MinHeap{}
    heap.Init(h)
    heap.Push(h, Item{node: k, dist: 0})

    for h.Len() > 0 {
        cur := heap.Pop(h).(Item)
        if cur.dist > dist[cur.node] {
            continue
        }
        for _, e := range graph[cur.node] {
            nd := cur.dist + e.cost
            if nd < dist[e.to] {
                dist[e.to] = nd
                heap.Push(h, Item{node: e.to, dist: nd})
            }
        }
    }

    answer := 0
    for i := 1; i <= n; i++ {
        if dist[i] == inf {
            return -1
        }
        if dist[i] > answer {
            answer = dist[i]
        }
    }

    return answer
}

复杂度分析

时间复杂度：$O(E \log E)$，其中 $E$ 是边数。凭的是每条边最多触发一次成功松弛、也就最多向堆里塞进一条记录，堆的规模上界是 $O(E)$，而每次入堆和出堆各是 $O(\log E)$。因为 $E \le V^2$，$\log E \le 2 \log V$，所以常写作 $O(E \log V)$。懒删除让堆里存在冗余记录，但它们只会被弹出后立刻跳过，不改变量级。

空间复杂度：$O(V + E)$。邻接表存下全部边是 $O(V + E)$，dist 数组是 $O(V)$，堆最坏装下 $O(E)$ 条记录。全程没有递归，不占调用栈。

关键点总结

「同时出发、等最后一个到达」这类措辞的标准翻译是「单源最短路，然后取全体最大值」。识别出这层翻译，题目就退化成了模板；识别不出，很容易误当成遍历题或 DP。

边权非负是贪心式最短路成立的唯一前提，也是选型的分水岭。面试时主动说一句「因为权值非负所以用 Dijkstra，若含负权要改 Bellman-Ford 或 SPFA」，等于把算法选择的理由讲透了。

堆优化的懒删除写法（弹出时用 d > dist[node] 判过期）是工程上的标准做法，比维护可减堆简单得多。凡是「堆里的元素会被更优值取代」的场景，都可以套这个模式。

距离数组的初值必须是一个真正的哨兵值，它同时承担「未访问」和「不可达」两个语义；收尾时靠它区分「路径长度为 0」和「根本走不到」，用 0 或 -1 当初值会让这两种情况混淆。

编号从 1 开始的图题，数组一律开 n + 1 长并让下标与编号对齐，比全篇写 -1 换算更不容易出错——图题里 0/1 下标混用是最高频的低级错误来源。

面试视角：这题几乎必被追问「$n$ 很小时还能怎么做」和「如果边权可能为负呢」。前者答 Floyd（$O(n^3)$，代码只有三重循环，$n \le 100$ 时完全够用），后者答 Bellman-Ford（松弛 $n-1$ 轮，$O(VE)$，还能顺带判负环）。能把三种最短路算法的适用边界一次说清，是这题的最高得分点。

易错点总结

建图方向写反：写成 graph[t[1]].add(new int[]{t[0], t[2]})，对 times = [[2,1,1],[2,3,1],[3,4,1]]、k = 2 会从 2 出发无路可走，返回 -1 而不是 2。

顺手加了反向边当无向图：对 times = [[1,2,1],[2,3,7],[1,3,4],[2,1,2]]、k = 1，无向化后 dist[3] 会被算成 4 以下的某个更小值，掩盖掉真实的有向传播代价。

数组开成 new int[n]：编号 n 的节点访问 dist[n] 直接抛 ArrayIndexOutOfBoundsException；n = 1、k = 1 时会在 dist[k] = 0 这一行就崩。

收尾时忘了 dist 里还有无穷大：直接 max 全部值，对 times = [[1,2,1]]、n = 3、k = 1 会返回 Integer.MAX_VALUE 而不是 -1。

收尾只扫 dist[1..n-1] 或从 0 开始扫：从 0 扫会把永远为无穷大的哨兵位 dist[0] 算进去，任何输入都返回 -1。

松弛后入堆的仍是旧距离：写成 pq.offer(new int[]{d, next}) 而不是 {dist[next], next}，堆的排序键与真实距离脱节，弹出顺序失序，times = [[1,2,10],[1,3,1],[3,2,1]]、k = 1 这类「绕路更短」的图会得到 10 而非 2。

无条件把邻居入堆而不判断是否真的缩短：去掉 if (dist[node] + w < dist[next]) 的判断，堆规模会随环的存在无限膨胀，稠密图上直接超时或内存溢出。

用 visited 布尔数组代替过期判断且在入堆时打标记：节点在首次入堆（而非首次出堆）时就被标记为已访问，后续更短的路径无法再更新它，times = [[1,2,10],[1,3,1],[3,2,1]]、k = 1 会返回 10 而不是 2。标记必须在出堆定稿时打。

比较器写成 (a, b) -> a[1] - b[1]：按节点编号而非距离排序，堆退化成任意顺序的容器，贪心前提被破坏，结果随输入而错。

Go 里 dist 初值用 math.MaxInt64：松弛时算 cur.dist + e.cost 会整数溢出成负数，反而「优于」任何真实距离，导致不可达节点被误判成可达；应当像代码里那样取 1 << 60 这类留足余量的哨兵。

忘记把起点自身计入答案：只在被松弛过的节点里取最大值，n = 1、k = 1、times = [] 会因为没有任何松弛而返回初始值以外的东西；正确答案是 0。

相似题目

题目	难度	考察点
787. K 站中转内最便宜的航班	中等	多出「中转次数上限」这一维状态，贪心前提失效，需按轮次松弛的 Bellman-Ford
1631. 最小体力消耗路径	中等	路径代价从「边权累加」换成「边权取最大」，松弛式改为取 max，也可改用二分加连通判定
778. 水位上升的泳池中游泳	困难	同为瓶颈路径，但代价定义在格点权值上，堆里存的是当前路径的最高水位
505. 迷宫 II	中等	边不是显式给出的，球一路滚到墙才算一条边，需要先把滚动过程折算成权重
499. 迷宫 III	困难	在 505 之上追加字典序最小的路径要求，堆的比较器要变成「距离优先、路径串次之」
1334. 阈值距离内邻居最少的城市	中等	需要全源最短路而非单源，节点数小，直接三重循环的 Floyd 比跑 $n$ 次本题解法更简洁
1091. 二进制矩阵中的最短路径	中等	边权全为 1，此时堆是多余的，普通队列 BFS 就能保证首次到达即最短
815. 公交路线	困难	建图对象要从站点换成路线，抽象出正确的节点定义比跑最短路本身更难