DeepSeek LeetCode 2642. 设计可以求最短路径的图类 Python3实现

下面是 LeetCode 2642「设计可以求最短路径的图类」的 Python3 实现。

题目理解

设计一个 Graph 类，支持：

1. 初始化：__init__(self, n, edges) - n 个节点（0 到 n-1），edges 为有向边 [from, to, cost]
2. 添加边：addEdge(self, edge) - 添加一条新边
3. 求最短路径：shortestPath(self, node1, node2) - 返回 node1 到 node2 的最短路径长度，不存在返回 -1

完整实现代码

方案一：Dijkstra 算法（推荐）

```python
import heapq
from typing import List

class 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 = edge
self.graph[u].append((v, cost))

def shortestPath(self, node1: int, node2: int) -> int:
# Dijkstra 算法
dist = [float('inf')] * self.n
dist[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 + cost
if new_dist < dist[v]:
dist[v] = new_dist
heapq.heappush(pq, (new_dist, v))

return -1 if dist[node2] == float('inf') else dist[node2]
```

方案二：使用堆优化的 Dijkstra（更简洁）

```python
import heapq
from typing import List

class Graph:
def __init__(self, n: int, edges: List[List[int]]):
self.n = n
self.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 = edge
self.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:
continue
dist[u] = d

if u == node2:
return d

for v, w in self.graph[u]:
if v not in dist:
heapq.heappush(heap, (d + w, v))

return -1
```

方案三：Floyd-Warshall 预计算（适合多次查询）

```python
from typing import List

class 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] = 0

for u, v, cost in edges:
self.dist[u][v] = min(self.dist[u][v], cost)

# 运行 Floyd-Warshall
self._floyd_warshall()

def _floyd_warshall(self):
n = self.n
for 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.n
for 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)
· addEdge：O(1)
· shortestPath：O((V + E) log V)
· 空间复杂度：O(V + E)
· 适用场景：查询次数适中，代码简洁

方案二（字典版本）

· 类似方案一，但使用字典记录已访问节点
· 常数因子稍小，但逻辑相同

方案三（Floyd-Warshall）

· 初始化：O(V³)
· addEdge：O(V²)
· shortestPath：O(1)
· 空间复杂度：O(V²)
· 适用场景：查询次数非常多（> V² 次）

关键技巧

1. 使用 heapq 实现优先队列：Python 标准库，效率高
2. 剪枝优化：当弹出节点为目标节点时立即返回
3. 懒删除：通过判断 curr_dist > dist[u] 跳过过期的堆条目
4. 无穷大表示：使用 float('inf') 或 math.inf
5. 类型提示：使用 typing.List 增强代码可读性

选择建议

· LeetCode 标准解法：方案一（Dijkstra）最常用
· 查询次数 ≤ 100：方案一或方案二
· 查询次数 ≥ 1000：方案三（Floyd 预计算）

根据题目约束（n ≤ 100，最多 100 次操作），方案一是最佳选择。