You need to enable JavaScript to run this app. 如何在Dijkstra算法中实现ending_ver及理解图的问题抽象
优惠活动
大模型
产品
解决方案
定价
更多

如何在Dijkstra算法中实现ending_ver及理解图的问题抽象

图结构的问题抽象逻辑

图的抽象本质是剥离现实问题的非核心细节,把所有同类问题拆解成可通用计算的三要素结构,对应映射关系非常直接:

  • 抽取问题中的所有独立决策对象,作为图的顶点:比如交通场景里的路口、电商场景里的商品、流程场景里的任务节点
  • 抽取对象之间的可通行/可跳转/可关联的连接关系,作为图的边:比如两个路口相邻通车道、商品之间存在推荐跳转、任务之间存在先后依赖
  • 给每条边量化对应的成本/收益属性,作为边的权重:比如通车道的通行时间、推荐跳转的用户点击率、任务衔接的人力成本

举个具象的例子:要解决“从家到地铁站的最短步行路线”问题,现实场景里有很多非核心干扰信息(路边的树、店铺招牌、红绿灯的时长),抽象成图的时候只需要保留三个核心要素,整个问题就简化为标准的图最短路径求解问题,不需要和现实细节纠缠。完成抽象后,不管现实问题的场景差异多大,只要符合这三个结构,都可以直接用图论的通用算法求解,不用针对每个场景从零搭建逻辑。

Dijkstra算法改造:支持指定起点返回最短路径

原代码仅能返回起点到全图所有顶点的最短距离数值,不支持路径回溯、也没有针对指定终点的优化,改造核心做三点调整:

  1. 新增ending_ver入参,指定需要查询的目标终点
  2. 新增前驱节点记录表,追踪每个顶点最短路径上的上一个邻接顶点,方便最终回溯拼接完整路径
  3. 增加提前终止逻辑:当优先队列弹出目标终点时,直接中断循环,无需遍历全图所有节点,提升运行效率

改造后完整可运行代码如下:

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

相关产品推荐
方舟 Agent Plan

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

最近更新时间:2026.11.14 13:24:04