不修改原始节点的情况下编写Dijkstra算法的代码
创始人
2025-01-10 10:30:29
0

在不修改原始节点的情况下编写Dijkstra算法的代码可以使用优先级队列(Priority Queue)来实现。

以下是一个示例代码:

import heapq

def dijkstra(graph, start):
    # 初始化距离字典,用于存储起始节点到其他节点的距离
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    
    # 创建优先级队列,用于存储节点及其到起始节点的距离
    queue = [(0, start)]
    
    while queue:
        current_distance, current_node = heapq.heappop(queue)
        
        # 如果当前节点已经被处理过,则跳过
        if current_distance > distances[current_node]:
            continue
        
        # 遍历当前节点的所有邻居节点
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            
            # 如果找到更短的路径,则更新距离字典和优先级队列
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))
    
    return distances

使用示例:

graph = {
    'A': {'B': 5, 'C': 2},
    'B': {'A': 5, 'C': 1, 'D': 3},
    'C': {'A': 2, 'B': 1, 'D': 2},
    'D': {'B': 3, 'C': 2}
}

distances = dijkstra(graph, 'A')
print(distances)

该代码使用了一个优先级队列来存储节点及其到起始节点的距离。在每次迭代中,从队列中弹出当前距离最小的节点,然后更新其邻居节点的距离。如果找到更短的路径,则更新距离字典和优先级队列。最终返回距离字典,其中包含了起始节点到所有其他节点的最短距离。

相关内容

热门资讯

透视教学!wpk透视工作室,w... 透视教学!wpk透视工作室,wpk模拟器多开,我来教教你(有挂规律)1、首先打开wpk模拟器多开最新...
透视辅助!wpk有那种辅助吗,... 透视辅助!wpk有那种辅助吗,wpk有作弊吗,安装教程(有挂方法)运wpk有那种辅助吗辅助工具,进入...
透视有挂!wpk免费辅助,wp... 透视有挂!wpk免费辅助,wpk真吗,切实教程(有挂解密)1、完成wpk免费辅助的残局,帮助玩家取得...
透视工具!wpk模拟器是什么,... 透视工具!wpk模拟器是什么,wpk透视是真的吗,力荐教程(有挂解密)小薇(透视辅助)致您一封信;亲...
透视计算!wpk俱乐部辅助器,... 透视计算!wpk俱乐部辅助器,wpk私人局有透视吗,辅助教程(有挂详情);一、wpk私人局有透视吗A...
透视最新!wpk安卓下载辅助,... 透视最新!wpk安卓下载辅助,wpk真吗,分享教程(有挂解说)1、下载好wpk安卓下载辅助辅助软件之...
透视规律!wpk刷入池率脚本,... 透视规律!wpk刷入池率脚本,wpk俱乐部怎么作弊,AI教程(有挂细节)1、wpk俱乐部怎么作弊系统...
透视软件!wpk辅助购买,wp... 透视软件!wpk辅助购买,wpk私人局有透视吗,存在挂教程(有挂插件);进入游戏-大厅左侧-新手福利...
透视中牌率!wpk有辅助器吗,... 透视中牌率!wpk有辅助器吗,wpk辅助,解说技巧(有挂方法)1、用户打开应用后不用登录就可以直接使...
透视辅助!wpk有那种辅助吗,... 透视辅助!wpk有那种辅助吗,如何下载wpk透视版,2025新版教程(有挂详情)1、进入游戏-大厅左...