LeetCode 743：网络延迟时间 | Dijkstra

LeetCode 743网络延迟时间 | Dijkstra引言网络延迟时间Network Delay Time是 LeetCode 第 743 题难度为 Medium。题目要求找到信号从某个节点出发到达所有节点所需的最短时间。算法实现import heapq def networkDelayTime(times, n, k): graph [[] for _ in range(n)] for u, v, w in times: graph[u - 1].append((v - 1, w)) dist [float(inf)] * n dist[k - 1] 0 pq [(0, k - 1)] while pq: d, u heapq.heappop(pq) if d dist[u]: continue for v, w in graph[u]: if dist[v] dist[u] w: dist[v] dist[u] w heapq.heappush(pq, (dist[v], v)) return max(dist) if max(dist) ! float(inf) else -1复杂度分析时间复杂度O(E log V)空间复杂度O(V E)总结单源最短路径问题使用 Dijkstra 算法解决。