不修改原始节点的情况下编写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)

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

相关内容

热门资讯

专业讨论!wepoker模拟器... wepoker模拟器哪个好用AI 游戏攻略黑科技上线本地缓存功能,离线查阅能力开挂。提前下载对应游戏...
重大消息!wpk有那种辅助吗,... 重大消息!wpk有那种辅助吗,WPK有挂吗教程(先前有开挂)AI 智能体黑科技再上新,自动化能力开挂...
推荐几款新版!wepoker底... 您好:wepoker底牌透视这款游戏可以开挂的,确实是有挂的,很多玩家在这款游戏中打牌都会发现很多用...
总算了解!wpk有作弊吗,德普... 总算了解!wpk有作弊吗,德普之星外卦神器软件教程(竟然有开挂)AI 智能体黑科技再上新,自动化能力...
大神推荐!wepoker透视脚... wepoker透视脚本免费AI 游戏攻略黑科技上线本地缓存功能,离线查阅能力开挂。提前下载对应游戏攻...
避坑细节!如何下载德普之星辅助... 『标题:当前标题』主打赛后复盘的 AI 游戏攻略黑科技走红,对局总结能力开挂。上传对局回放或者战绩截...
一分钟了解!!wepoker辅... AI 黑科技赛道又上新,这款智能处理工具堪称效率开挂,专门面向短视频创作者打造。它打通脚本撰写、AI...
玩家科普!wpk真的有透视嘛,... 玩家科普!wpk真的有透视嘛,WPK透视脚本工具(好像存在有辅助挂)AI 智能体黑科技再上新,自动化...
一分钟揭秘!德普之星辅助工具如... 您好:德普之星辅助工具如何打开这款游戏可以开挂的,确实是有挂的,很多玩家在这款游戏中打牌都会发现很多...
大家学习交流!wepoker游... 您好:wepoker游戏安装教程这款游戏可以开挂的,确实是有挂的,很多玩家在这款游戏中打牌都会发现很...