网络延迟时间 图解题解

这道题到底在问什么

输入

n=6, k=1, times=[[1,2,2],[1,3,5],[1,4,9],[2,3,1],[2,4,4],[3,4,2],[3,5,3],[4,5,1],[4,6,6],[5,6,2],[2,5,8],[3,6,9]]

输出

8

最优解：一步一步想明白

1. 3记住这句，下面每一帧都在套它。
2. 4源点是节点 1：到自己的距离 dist=0，其余节点先记成 ∞（还不知道怎么到）。
3. 5当前未确定的节点里，dist 最小的是节点 1（dist=0）。取出它——它的最短距离从此确定。
4. 6松弛 1→2：经过 1 走，dist[1]+2=2，比原来的 ∞ 更近 → 更新 dist[2]=2。
5. 7松弛 1→3：经过 1 走，dist[1]+5=5，比原来的 ∞ 更近 → 更新 dist[3]=5。
6. 8松弛 1→4：经过 1 走，dist[1]+9=9，比原来的 ∞ 更近 → 更新 dist[4]=9。
7. 9当前未确定的节点里，dist 最小的是节点 2（dist=2）。取出它——它的最短距离从此确定。
8. 10松弛 2→3：经过 2 走，dist[2]+1=3，比原来的 5 更近 → 更新 dist[3]=3。
9. 11松弛 2→4：经过 2 走，dist[2]+4=6，比原来的 9 更近 → 更新 dist[4]=6。
10. 12松弛 2→5：经过 2 走，dist[2]+8=10，比原来的 ∞ 更近 → 更新 dist[5]=10。
11. 13当前未确定的节点里，dist 最小的是节点 3（dist=3）。取出它——它的最短距离从此确定。
12. 14松弛 3→4：经过 3 走，dist[3]+2=5，比原来的 6 更近 → 更新 dist[4]=5。
13. 15松弛 3→5：经过 3 走，dist[3]+3=6，比原来的 10 更近 → 更新 dist[5]=6。
14. 16松弛 3→6：经过 3 走，dist[3]+9=12，比原来的 ∞ 更近 → 更新 dist[6]=12。
15. 17当前未确定的节点里，dist 最小的是节点 4（dist=5）。取出它——它的最短距离从此确定。
16. 18松弛 4→5：经过 4 走是 5+1=6，不比现有的 6 近 → 不更新。
17. 19松弛 4→6：经过 4 走，dist[4]+6=11，比原来的 12 更近 → 更新 dist[6]=11。
18. 20当前未确定的节点里，dist 最小的是节点 5（dist=6）。取出它——它的最短距离从此确定。
19. 21松弛 5→6：经过 5 走，dist[5]+2=8，比原来的 11 更近 → 更新 dist[6]=8。
20. 22当前未确定的节点里，dist 最小的是节点 6（dist=8）。取出它——它的最短距离从此确定。
21. 23所有节点都确定了。最大的 dist 是 8（节点最远的那个），就是信号传遍全网要的时间 → 答案 8。

⚠️ 容易写错的地方

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

import heapq
def networkDelayTime(times, n, k):
    g = {}
    for u, v, w in times:
        g.setdefault(u, []).append((v, w))
    dist = {}
    pq = [(0, k)]
    while pq:
        d, u = heapq.heappop(pq)
        if u in dist: continue
        dist[u] = d
        for v, w in g.get(u, []):
            if v not in dist:
                heapq.heappush(pq, (d + w, v))
    return max(dist.values()) if len(dist) == n else -1

#include <vector>
#include <queue>
using namespace std;
int networkDelayTime(vector<vector<int>>& times, int n, int k){
    vector<vector<pair<int,int>>> g(n + 1);
    for(auto& t : times) g[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, u] = pq.top(); pq.pop();
        if(d > dist[u]) continue;
        for(auto& [v, w] : g[u])
            if(d + w < dist[v]){ dist[v] = d + w; pq.push({dist[v], v}); }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){ if(dist[i] == INT_MAX) return -1; ans = max(ans, dist[i]); }
    return ans;
}

import java.util.*;
class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        List<int[]>[] g = new List[n + 1];
        for (int i = 1; i <= n; i++) g[i] = new ArrayList<>();
        for (int[] t : times) g[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], u = cur[1];
            if (d > dist[u]) continue;
            for (int[] e : g[u]) {
                int v = e[0], w = e[1];
                if (d + w < dist[v]) {
                    dist[v] = d + w;
                    pq.offer(new int[]{dist[v], v});
                }
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) return -1;
            ans = Math.max(ans, dist[i]);
        }
        return ans;
    }
}

复杂度

面试官可能追问