下面是 LeetCode 2642「设计可以求最短路径的图类」的 Python3 实现。题目理解设计一个 Graph 类支持1. 初始化__init__(self, n, edges) - n 个节点0 到 n-1edges 为有向边 [from, to, cost]2. 添加边addEdge(self, edge) - 添加一条新边3. 求最短路径shortestPath(self, node1, node2) - 返回 node1 到 node2 的最短路径长度不存在返回 -1完整实现代码方案一Dijkstra 算法推荐pythonimport heapqfrom typing import Listclass Graph:def __init__(self, n: int, edges: List[List[int]]):self.n n# 邻接表graph[u] [(v, cost), ...]self.graph [[] for _ in range(n)]for u, v, cost in edges:self.graph[u].append((v, cost))def addEdge(self, edge: List[int]) - None:u, v, cost edgeself.graph[u].append((v, cost))def shortestPath(self, node1: int, node2: int) - int:# Dijkstra 算法dist [float(inf)] * self.ndist[node1] 0# 优先队列(距离, 节点)pq [(0, node1)]while pq:curr_dist, u heapq.heappop(pq)# 如果当前距离大于记录的距离跳过if curr_dist dist[u]:continue# 到达目标节点可以提前返回if u node2:return curr_dist# 遍历邻接节点for v, cost in self.graph[u]:new_dist curr_dist costif new_dist dist[v]:dist[v] new_distheapq.heappush(pq, (new_dist, v))return -1 if dist[node2] float(inf) else dist[node2]方案二使用堆优化的 Dijkstra更简洁pythonimport heapqfrom typing import Listclass Graph:def __init__(self, n: int, edges: List[List[int]]):self.n nself.graph [[] for _ in range(n)]for u, v, w in edges:self.graph[u].append((v, w))def addEdge(self, edge: List[int]) - None:u, v, w edgeself.graph[u].append((v, w))def shortestPath(self, node1: int, node2: int) - int:heap [(0, node1)]dist {}while heap:d, u heapq.heappop(heap)if u in dist:continuedist[u] dif u node2:return dfor v, w in self.graph[u]:if v not in dist:heapq.heappush(heap, (d w, v))return -1方案三Floyd-Warshall 预计算适合多次查询pythonfrom typing import Listclass Graph:def __init__(self, n: int, edges: List[List[int]]):self.n n# 距离矩阵INF float(inf)self.dist [[INF] * n for _ in range(n)]for i in range(n):self.dist[i][i] 0for u, v, cost in edges:self.dist[u][v] min(self.dist[u][v], cost)# 运行 Floyd-Warshallself._floyd_warshall()def _floyd_warshall(self):n self.nfor k in range(n):for i in range(n):for j in range(n):if self.dist[i][k] self.dist[k][j] self.dist[i][j]:self.dist[i][j] self.dist[i][k] self.dist[k][j]def addEdge(self, edge: List[int]) - None:u, v, cost edge# 如果新边更短更新并重新计算if cost self.dist[u][v]:self.dist[u][v] cost# 更新受影响的路径n self.nfor i in range(n):for j in range(n):if self.dist[i][u] cost self.dist[v][j] self.dist[i][j]:self.dist[i][j] self.dist[i][u] cost self.dist[v][j]def shortestPath(self, node1: int, node2: int) - int:return -1 if self.dist[node1][node2] float(inf) else self.dist[node1][node2]使用示例python# 测试代码if __name__ __main__:# 初始化4个节点边列表edges [[0, 1, 1], [1, 2, 2], [2, 3, 3]]graph Graph(4, edges)print(graph.shortestPath(0, 3)) # 输出: 6 (0-1-2-3)print(graph.shortestPath(0, 2)) # 输出: 3 (0-1-2)# 添加新边graph.addEdge([0, 2, 2])print(graph.shortestPath(0, 3)) # 输出: 5 (0-2-3)# 不存在路径print(graph.shortestPath(3, 0)) # 输出: -1# 测试另一种初始化方式print(\n--- 测试多个节点 ---)graph2 Graph(5, [[0, 1, 10], [0, 2, 5], [1, 3, 1], [2, 3, 9], [3, 4, 2]])print(graph2.shortestPath(0, 4)) # 输出: 13 (0-1-3-4)graph2.addEdge([2, 4, 6])print(graph2.shortestPath(0, 4)) # 输出: 11 (0-2-4)复杂度分析方案一Dijkstra· 初始化O(E)· addEdgeO(1)· shortestPathO((V E) log V)· 空间复杂度O(V E)· 适用场景查询次数适中代码简洁方案二字典版本· 类似方案一但使用字典记录已访问节点· 常数因子稍小但逻辑相同方案三Floyd-Warshall· 初始化O(V³)· addEdgeO(V²)· shortestPathO(1)· 空间复杂度O(V²)· 适用场景查询次数非常多 V² 次关键技巧1. 使用 heapq 实现优先队列Python 标准库效率高2. 剪枝优化当弹出节点为目标节点时立即返回3. 懒删除通过判断 curr_dist dist[u] 跳过过期的堆条目4. 无穷大表示使用 float(inf) 或 math.inf5. 类型提示使用 typing.List 增强代码可读性选择建议· LeetCode 标准解法方案一Dijkstra最常用· 查询次数 ≤ 100方案一或方案二· 查询次数 ≥ 1000方案三Floyd 预计算根据题目约束n ≤ 100最多 100 次操作方案一是最佳选择。
