如何在Dijkstra算法中实现ending_ver及理解图的问题抽象
图结构的问题抽象逻辑
图的抽象本质是剥离现实问题的非核心细节,把所有同类问题拆解成可通用计算的三要素结构,对应映射关系非常直接:
- 抽取问题中的所有独立决策对象,作为图的顶点:比如交通场景里的路口、电商场景里的商品、流程场景里的任务节点
- 抽取对象之间的可通行/可跳转/可关联的连接关系,作为图的边:比如两个路口相邻通车道、商品之间存在推荐跳转、任务之间存在先后依赖
- 给每条边量化对应的成本/收益属性,作为边的权重:比如通车道的通行时间、推荐跳转的用户点击率、任务衔接的人力成本
举个具象的例子:要解决“从家到地铁站的最短步行路线”问题,现实场景里有很多非核心干扰信息(路边的树、店铺招牌、红绿灯的时长),抽象成图的时候只需要保留三个核心要素,整个问题就简化为标准的图最短路径求解问题,不需要和现实细节纠缠。完成抽象后,不管现实问题的场景差异多大,只要符合这三个结构,都可以直接用图论的通用算法求解,不用针对每个场景从零搭建逻辑。
Dijkstra算法改造:支持指定起点返回最短路径
原代码仅能返回起点到全图所有顶点的最短距离数值,不支持路径回溯、也没有针对指定终点的优化,改造核心做三点调整:
- 新增
ending_ver入参,指定需要查询的目标终点 - 新增前驱节点记录表,追踪每个顶点最短路径上的上一个邻接顶点,方便最终回溯拼接完整路径
- 增加提前终止逻辑:当优先队列弹出目标终点时,直接中断循环,无需遍历全图所有节点,提升运行效率
改造后完整可运行代码如下:
import heapq def dijkstras(grh, str_ver, ending_ver): # 初始化距离字典:记录起点到每个顶点的最短距离 distances = {vertex: float('infinity') for vertex in grh} distances[str_ver] = 0 # 新增:初始化前驱节点字典,记录最短路径上每个顶点的上一个节点 previous_vertex = {vertex: None for vertex in grh} pq = [(0, str_ver)] while len(pq) > 0: current_distance, current_vertex = heapq.heappop(pq) # 节点重复入队的过滤逻辑保持不变 if current_distance > distances[current_vertex]: continue # 新增:弹出的当前节点就是目标终点时,直接终止循环,无需继续遍历 if current_vertex == ending_ver: break for neighbor, weight in grh[current_vertex].items(): distance = current_distance + weight if distance < distances[neighbor]: distances[neighbor] = distance # 新增:更新邻接节点的前驱为当前节点 previous_vertex[neighbor] = current_vertex heapq.heappush(pq, (distance, neighbor)) # 回溯拼接完整最短路径 shortest_path = [] current = ending_ver # 从终点往起点回溯,直到回溯到起点为止 while current is not None: shortest_path.append(current) current = previous_vertex[current] # 反转列表得到从起点到终点的正向路径 shortest_path.reverse() # 校验路径连通性:如果回溯完发现路径第一个节点不是起点,说明两个点不连通 if shortest_path[0] != str_ver: return float('infinity'), [] return distances[ending_ver], shortest_path
调用示例
# 测试用图结构 test_graph = { 'A': {'B': 2, 'C': 5}, 'B': {'C': 1, 'D': 3}, 'C': {'D': 1}, 'D': {} } # 查询A点到D点的最短路径 min_dist, path = dijkstras(test_graph, 'A', 'D') # 最终输出结果:(4, ['A', 'B', 'C', 'D'])
内容的提问来源于stack exchange,提问作者user14780713
相关产品推荐
相关产品推荐

