LeetCode 网络延迟时间题解
题目描述
给定一个网络和信号源节点，计算信号到达所有其他节点所需的最长时间。
示例：
输入：times = [[2,1,1],[2,3,1],[3,4,1]],n = 4,k = 2
输出：2
解题思路
方法：Dijkstra 算法
思路：
- 使用 Dijkstra 算法计算从源节点到所有其他节点的最短路径。
- 返回最大最短路径。
复杂度分析：
- 时间复杂度：O(E log V)。
- 空间复杂度：O(V)。
代码实现
import heapq def network_delay_time(times, n, k): graph = [[] for _ in range(n + 1)] for u, v, w in times: graph[u].append((v, w)) dist = [float('inf')] * (n + 1) dist[k] = 0 pq = [(0, k)] while pq: d, u = heapq.heappop(pq) if d > dist[u]: continue for v, w in graph[u]: if dist[u] + w < dist[v]: dist[v] = dist[u] + w heapq.heappush(pq, (dist[v], v)) max_dist = max(dist[1:]) return max_dist if max_dist != float('inf') else -1 # 测试 def test_network_delay_time(): times = [[2, 1, 1], [2, 3, 1], [3, 4, 1]] n, k = 4, 2 print(network_delay_time(times, n, k)) # 输出：2 if __name__ == "__main__": test_network_delay_time()总结
网络延迟时间是 Dijkstra 算法的典型应用，计算信号到达所有节点的最长时间。
