You need to enable JavaScript to run this app. Python实现有向图分段寻路:经中间点的最短路径求解与代码优化
优惠活动
大模型
产品
解决方案
定价
更多

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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.14 15:36:04