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 算法解决。