LeetCode 743. 网络延迟时间

2021-12-08 HGNULB 约 8 分钟

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

分类

LeetCode CodeTop 中等未解决 2-5 腾讯字节华为微软

题目描述

✅ 743. 网络延迟时间

题意分析

有向边 [u, v, w] 表示信号从 u 传到 v 需要 w 个时间单位。从节点 k 同时向能够到达的方向传播，求所有节点都收到信号时的最早时间；只要有节点无法收到，就返回 -1。

各条路线可以并行传播，所以某个节点收到信号的时刻，是起点到它的最短路径长度；整个网络完成的时刻，是这些最短时间里的最大值，不是路径时间的总和。边是有方向的，不能自行添加反向传播。

解法：Dijkstra 最短路

核心思路

[!blue]

题目边权非负，可以使用 Dijkstra。dist[v] 保存目前已发现的起点到 v 的最短距离，起点为零，其余先记不可达。小顶堆保存“候选距离和节点”，每次优先处理距离最小的记录。

一个节点以当前最小有效距离出堆时，这个距离已经不可能再被后面的路线缩短。因为任何尚未完成的更短路线，都必须先经过另一个待处理节点；那个节点的距离不会小于当前堆顶，而再加非负边权也不可能变得更小。这就是可以按距离从小到大确定最短路的依据。

对当前节点的每条出边，尝试用当前最短距离加边权到达邻居。如果比邻居已知距离更短，就更新 dist 并把新候选放入堆，这个过程称为松弛。只在严格缩短时入堆，等长路径和零权环不会不断制造无效记录。

堆没有原地删除旧距离记录，所以同一节点可能同时有旧、新两个候选。弹出时若记录距离大于 dist[node]，说明它已被更短路径替代，应直接跳过；第一次入堆只表示发现一条路径，不能此时就禁止后续更新。

堆只会接收已找到的有限距离，不会拿不可达哨兵继续做加法。Go 使用 n * 100 + 1 作为哨兵：题目每条边最多为 100，非负权最短路可以去掉重复绕行，至多保留 n - 1 条边，因此所有真正的最短距离都小于该值。最后先检查是否有不可达节点，再对有效距离取最大值。

解题步骤

按输入方向建立邻接表，保存每条出边的终点和传播时间。

将起点距离置零、其余置为不可达，把起点候选加入小顶堆。

弹出当前最小候选，若已经过期则跳过。

遍历当前节点出边，只有得到更短距离时才更新邻居并把新候选入堆。

堆处理完后，任意节点仍不可达就返回 -1；否则返回所有节点最短距离中的最大值。

代码实现

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;
    }
}

import "container/heap"

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]})
    }

    // 最短简单路径至多经过 n 减一条、每条不超过一百的边
    inf := n*100 + 1
    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(V + E\log(E + 1))$，V 为节点数、E 为边数。初始化为 $O(V + E)$，每条边至多成功松弛一次，堆中包含旧记录时规模至多为 $O(E)$。

空间复杂度：$O(V + E)$，邻接表保存全部边，距离表保存全部节点，堆保存候选记录。

关键点总结

[!green]

非负边权保证最小有效候选出堆时可以确定最短距离。

距离数组保存当前最优，堆只负责安排处理顺序，旧候选通过出堆检查丢弃。

严格缩短才入堆，避免环和等长路线重复扩展。

最终结果是全部最短时间的最大值，并且必须先排除不可达节点。

易错点总结

[!yellow]

将输入边当成无向边，会让信号走到本来不可达的节点。

节点第一次入堆就锁定距离，会漏掉稍后发现的更短绕行路线。

对每个邻居无条件入堆，会在环上反复产生记录，破坏有限处理次数。

不过滤过期候选，会重复扩展已经被更好路径替代的旧状态。

不判断不可达就直接取距离最大值，会返回哨兵，而不是题目要求的 -1。

将各节点距离相加，忽略了不同路线同时传播，只需等待最晚收到的节点。

相似题目

题目	难度	关联与区别
787. K 站中转内最便宜的航班	中等	同样求有向带权图最短路，原题还限制中转次数，需要把步数纳入状态。
1514. 概率最大的路径	中等	同样进行最优路径松弛，原题累乘概率并最大化，本题累加时间并最小化。
补充题 191. 带权有向图中两点间的最短距离	中等	都可用 Dijkstra 处理非负权最短路；本题要汇总所有节点，补充题只查询两点。
1631. 最小体力消耗路径	中等	用优先队列取当前最优距离并松弛邻边；本题传播源点到各点的加法距离，该题路径代价改为沿途最大边权。
778. 水位上升的泳池中游泳	困难	用优先队列取当前最优距离并松弛邻边；本题传播源点到各点的加法距离，该题路径代价改为沿途最高水位。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2021/24042204

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！