Python实现有向图分段寻路:经中间点的最短路径求解与代码优化
有向图分段最短路径实现修正
现有代码核心问题
- 存储结构缺陷:仅用
(起点,终点)元组作为字典键存储直连边,未构建图的邻接关系,完全不支持多跳路径的遍历计算 - 判断逻辑硬伤:直接通过字典键存在性判断直连边,键不存在时会触发
KeyError异常,且完全未考虑多节点中转的最短路径场景 - 字典使用不规范:直接通过键索引判断边存在性,未使用安全的字典取值方式,极易触发运行时错误
- 冗余无效判断:
len(d) < 2即判定为不可达的逻辑无实际依据,与路径是否可达没有关联
实现思路
题目要求的严格经过指定中间点的最短路径,本质是两次独立的最短路径计算:
总最短耗时 = 从起点
start到中间点mid的最短路径耗时 + 从中间点mid到终点end的最短路径耗时
只要任意一段路径不可达,整体就没有可行方案。由于题目中的边权为正的通行耗时,使用Dijkstra算法即可高效求解最短路径,覆盖任意多跳中转的场景。
修正后完整代码
import heapq def dijkstra(graph, start, end, all_nodes): # 初始化所有节点的最短距离为无穷大 dist = {node: float('inf') for node in all_nodes} dist[start] = 0 # 优先队列存储元素:(当前累计通行耗时, 当前所在节点) heap = [] heapq.heappush(heap, (0, start)) while heap: current_cost, current_node = heapq.heappop(heap) # 提前到达终点时直接返回当前耗时,减少不必要的遍历 if current_node == end: return current_cost # 若当前路径累计耗时比已记录的最短路径更长,直接跳过 if current_cost > dist[current_node]: continue # 遍历当前节点所有邻接的有向边,无邻接边时返回空列表 for next_node, weight in graph.get(current_node, []): new_cost = current_cost + weight # 找到更短路径时更新距离,加入优先队列 if new_cost < dist[next_node]: dist[next_node] = new_cost heapq.heappush(heap, (new_cost, next_node)) # 遍历完成仍未到达目标点,标记为不可达 return float('inf') # 读取输入构建邻接表 locations, roads = map(int, input().split()) graph = {} all_nodes = set() # 收集所有出现过的节点,避免字典键缺失报错 for _ in range(roads): l1, l2, t = map(int, input().split()) all_nodes.add(l1) all_nodes.add(l2) if l1 not in graph: graph[l1] = [] graph[l1].append((l2, t)) start, mid, end = map(int, input().split()) # 把查询用到的三个节点也加入总节点集合,覆盖孤立节点场景 all_nodes.add(start) all_nodes.add(mid) all_nodes.add(end) # 分别计算两段路径的最短耗时 cost_start_to_mid = dijkstra(graph, start, mid, all_nodes) cost_mid_to_end = dijkstra(graph, mid, end, all_nodes) if cost_start_to_mid == float('inf') or cost_mid_to_end == float('inf'): print("impossible") else: print(cost_start_to_mid + cost_mid_to_end)
效果验证
- 匹配第一个示例输入时,计算得到start→mid耗时1、mid→end耗时1,总输出2,符合预期
- 匹配第二个示例输入时,mid到end无可达路径,输出
impossible,符合预期 - 支持任意多跳中转的复杂场景,比如start到mid经过3个中转节点、mid到end经过2个中转节点的路径,都能正确计算最小总耗时
内容的提问来源于stack exchange,提问作者lambduh
相关产品推荐
相关产品推荐

