网络延迟时间 图解题解

这道题到底在问什么

edges

2→1(1), 2→3(4), 1→3(1), 3→4(1)

k

2

输出

3

最优解：一步一步想明白

1. 3最朴素的做法：每一轮在所有还没敲定的点里线性扫一遍，挑出当前 dist 最小的那个去确定。点一多，每轮都把全部距离重新比一遍，大量重复比较。
2. 4转折：与其每轮线性扫找最小，不如把 (距离, 点) 全丢进最小堆，弹出即取到当前最近的点。它一旦弹出，最短距离就敲定(非负权保证后面不会更短)，再用它去松弛邻居：邻居新距离更短才更新并入堆。能用这招的前提是边权非负。
3. 5其余 dist=∞建带权邻接表。源点 2 的 dist=0，放进最小堆 (0,2)；其余点 dist 视为 ∞。边上的数字是权(用时)。
4. 6pop (0,2)，2 done弹出堆顶 (0,2)，它的距离 0 就是 2 的最终最短距离，点 2 敲定(done)。接下来要逐条松弛它指出去的边 2→1 和 2→3。
5. 7dist[1]=1, dist[3]=4松弛 2 的两条出边：dist[1]=0+1=1、dist[3]=0+4=4，都比 ∞ 小，更新并各自入堆 (1,1)、(4,3)。注意 3 暂时是 4，后面会被改短。
6. 8dist[3]: 4 → 2弹出 (1,1)，点 1 敲定。松弛边 1→3：新距离 1+1=2，比旧的 4 更短！更新 dist[3]=2 并把 (2,3) 入堆。堆里此刻同时有旧的 (4,3) 和新的 (2,3)——同一个点可能多次入堆。
7. 9dist[4]=3弹出更小的 (2,3)，它的距离 2 与 dist[3] 一致，是有效记录，点 3 敲定。松弛边 3→4：dist[4]=2+1=3，入堆 (3,4)。
8. 104 没有邻居弹出 (3,4)，点 4 敲定。它没有出边，不松弛任何点。堆里只剩一个 (4,3)——这是点 3 早先的旧记录。
9. 114 大于 dist[3]=2 → skip负例：弹出 (4,3)，但它带的距离 4 大于现在的 dist[3]=2，是被更短路径淘汰掉的过期记录——直接 continue 跳过，不重复松弛。这就是代码里那行 if d 大于 dist[u]: continue 的作用。
10. 12dist=[_,1,0,2,3]，max=3堆空了，四个点全部敲定：dist[2]=0、dist[1]=1、dist[3]=2、dist[4]=3。信号传遍全网的时间 = 所有最短距离里的最大值 = 3。若有某个点仍是 ∞(没进过 dist)，说明传不到，返回 −1。
11. 15和拓扑排序的 BFS 区别只有一点：拓扑用普通队列(谁先来谁先出)，带权最短路必须用最小堆按距离取点，否则会先确定一个其实还能更短的点，结果就错了。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

import heapq
class Solution:
    def networkDelayTime(self, times, n, k):
        graph = [[] for _ in range(n + 1)]
        for u, v, w in times:
            graph[u].append((v, w))
        dist = [10**18] * (n + 1)
        dist[k] = 0
        heap = [(0, k)]
        while heap:
            d, node = heapq.heappop(heap)
            if d > dist[node]:        # 过期记录：已被更短路更新过，跳过
                continue
            for nxt, w in graph[node]:
                if d + w < dist[nxt]:  # 松弛
                    dist[nxt] = d + w
                    heapq.heappush(heap, (d + w, nxt))
        ans = max(dist[1:])
        return -1 if ans == 10**18 else ans

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<pair<int,int>>> graph(n + 1);
        for (auto& t : times) graph[t[0]].push_back({t[1], t[2]});
        vector<int> dist(n + 1, INT_MAX);
        dist[k] = 0;
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
        pq.push({0, k});
        while (!pq.empty()) {
            auto [d, node] = pq.top(); pq.pop();
            if (d > dist[node]) continue;          // 过期记录，跳过
            for (auto& [nxt, w] : graph[node])
                if (d + w < dist[nxt]) {           // 松弛
                    dist[nxt] = d + w;
                    pq.push({dist[nxt], nxt});
                }
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) ans = max(ans, dist[i]);
        return ans == INT_MAX ? -1 : ans;
    }
};

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], node = cur[1];
            if (d > dist[node]) continue;          // 过期记录，跳过
            for (int[] e : graph[node])
                if (d + e[1] < dist[e[0]]) {       // 松弛
                    dist[e[0]] = d + e[1];
                    pq.offer(new int[]{dist[e[0]], e[0]});
                }
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) ans = Math.max(ans, dist[i]);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

# 非负权单源最短路都套这个骨架
dist = {src: 0}; heap = [(0, src)]
while heap:
    d, u = heappop(heap)               # 取当前最近的点
    if d > dist.get(u, INF): continue  # 过期记录跳过
    for v, w in g[u]:
        if d + w < dist.get(v, INF):   # 能松弛得更短
            dist[v] = d + w; heappush(heap, (dist[v], v))

复杂度

面试官可能追问