网络延迟时间如何用 Dijkstra 求最晚到达时间？

简化版

网络延迟时间是单源最短路径问题：从源点 k 出发，求信号到每个节点的最短时间。边权非负时用 Dijkstra，最后取所有最短距离里的最大值；如果有节点不可达，返回 -1。

详细版

先把 times 建成邻接表，u -> (v, w) 表示从 u 到 v 需要 w 时间。用 dist[i] 记录从 k 到 i 的当前最短时间，小根堆每次取出距离最小的节点并松弛它的出边。遍历结束后，如果某个 dist 仍是无穷大，说明信号到不了；否则答案是 max(dist[1..n])，因为所有节点都收到信号的时间由最慢那个节点决定。

复杂度是 O((V+E) log V)，适合稀疏图。题目边权是正数，所以 Dijkstra 的贪心前提成立。

完整版教学

一、题目为什么不是普通 BFS

普通 BFS 适合所有边权相同的图，因为每走一条边成本一样，层数就是距离。但网络延迟里的边有不同耗时，走 1 条边不一定比走 2 条边快，所以不能只看边数。

1 -> 2  cost 100
1 -> 3  cost 1
3 -> 2  cost 1

从 1 到 2，直接边只走 1 条但耗时 100；经过 3 走 2 条边但耗时 2。BFS 会优先认为 1 条边更近，Dijkstra 才会按累计时间比较。

二、Dijkstra 在这题里的含义

Dijkstra 的 dist[x] 表示信号从源点 k 到节点 x 的最短到达时间。小根堆里存 (当前时间, 节点)，每次弹出当前最早能确定的节点，再用它更新邻居。

变量	含义
`dist[i]`	k 到 i 的最短已知时间
`pq`	候选到达事件，按时间从小到大
`adj[u]`	u 能直接发送到的节点和耗时
`answer`	所有可达节点最短时间的最大值

“最大值”这一步很容易被忽略：Dijkstra 求出的是每个节点最早收到信号的时间，而题目问所有节点都收到，需要等最晚收到的节点。

三、代码实现骨架

实现时要注意节点通常从 1 编号，数组开 n + 1。堆里可能有过期记录，所以弹出后如果 time > dist[u] 就跳过。

int networkDelayTime(int[][] times, int n, int k) {
    List<int[]>[] adj = new ArrayList[n + 1];
    for (int i = 1; i <= n; i++) adj[i] = new ArrayList<>();
    for (int[] e : times) adj[e[0]].add(new int[]{e[1], e[2]});

    int INF = 1_000_000_000;
    int[] dist = new int[n + 1];
    Arrays.fill(dist, INF);
    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 t = cur[0], u = cur[1];
        if (t > dist[u]) continue;
        for (int[] e : adj[u]) {
            int v = e[0], w = e[1];
            if (t + w < dist[v]) {
                dist[v] = t + w;
                pq.offer(new int[]{dist[v], v});
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) ans = Math.max(ans, dist[i]);
    return ans == INF ? -1 : ans;
}

这里用 t + w 而不是 dist[u] + w 也可以，因为已经跳过了过期记录；为了表达更统一，也可以写成 dist[u] + w。

四、用数字例子走一遍

假设 n=4, k=2，边为 2->1(1), 2->3(1), 3->4(1)。初始化 dist[2]=0，堆里是 (0,2)。弹出 2 后，更新 1 和 3，得到 dist[1]=1, dist[3]=1。弹出 3 后，更新 4，得到 dist[4]=2。

2
|1
v
1

2 --1--> 3 --1--> 4

dist: [1]=1, [2]=0, [3]=1, [4]=2
answer = max = 2

答案是 2，因为节点 4 最晚收到。不是 3 条边数量，也不是最短路径条数，而是最大最短到达时间。

五、不可达节点怎么处理

如果图不是从 k 可达所有节点，某些 dist 会一直是无穷大。此时题目要求返回 -1，表示信号无法通知所有节点。

例如 n=3, k=1，只有边 1->2(5)，节点 3 没有任何路径可达。Dijkstra 结束后 dist[3]=INF，即使 2 能在 5 秒收到，也不能说全网延迟是 5，因为还有节点永远收不到。

六、和 Floyd、Bellman-Ford 怎么区分

算法	适用	在本题中的选择
BFS	无权或等权图	边权不同，不合适
Dijkstra	单源、非负权	最匹配
Bellman-Ford	单源、可负权	可用但通常更慢
Floyd	所有点对最短路	过重，不需要

如果面试官追问负权边，Dijkstra 的前提会失效，应改用 Bellman-Ford。但网络延迟这类题的时间成本通常为正数，Dijkstra 是标准答案。

七、常见误区与追问

记忆钩子：Dijkstra 给每个点一个“最早收到时间”，题目答案取这些时间里的最晚者。

误区：返回源点到某个终点的最短路。 这题没有指定终点，要求所有节点都收到，所以要取 max(dist)。
误区：用 BFS 按层数求。 边权不同，层数不等于时间，必须按累计权重排序。
误区：忽略不可达节点。 只要有一个节点 dist=INF，答案就是 -1。
追问：为什么堆里会有过期记录？ 一个节点可能先以较大距离入堆，后来被更短路径更新；旧记录弹出时要跳过。
追问：复杂度是多少？ 邻接表加小根堆通常是 O((V+E) log V)，空间 O(V+E)。
追问：如果要求所有点到所有点的延迟呢？ 那是多源或全源最短路问题，可考虑多次 Dijkstra 或 Floyd，取决于图规模。

八、加强记忆

网络延迟时间是 Dijkstra 的应用题，不要只背算法名。建图后从源点 k 求单源最短路，dist[i] 是节点 i 最早收到信号的时间；全网完成时间是所有 dist 的最大值；有无穷大说明不可达，返回 -1。边权非负是 Dijkstra 能成立的关键前提。

简化版

详细版