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

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

相关内容

热门资讯

外挂模块!约局吧德州有挂吗,来... 外挂模块!约局吧德州有挂吗,来玩app 德州 辅助-果然是真的有辅助脚本(哔哩哔哩)1、下载好约局吧...
外挂手筋!德扑圈透视,智星德州... 外挂手筋!德扑圈透视,智星德州插件2024最新版-竟然真的是有辅助神器(哔哩哔哩)智星德州插件202...
外挂手段!wepoker透视有... 外挂手段!wepoker透视有吗,德普之星透视-果然真的有辅助方法(哔哩哔哩)1、完成wepoker...
外挂教程书!拱趴大菠萝挂怎么安... 外挂教程书!拱趴大菠萝挂怎么安装,竞技联盟破解版最新版-切实有辅助攻略(哔哩哔哩)1、拱趴大菠萝挂怎...
外挂步骤!哈糖大菠萝可以开挂吗... 外挂步骤!哈糖大菠萝可以开挂吗,德扑圈有透视吗-本来真的有辅助攻略(哔哩哔哩)亲,关键说明,哈糖大菠...
外挂绝活!拱趴大菠萝万能挂图解... 外挂绝活!拱趴大菠萝万能挂图解,约局吧辅助器-一直一直都是有辅助方法(哔哩哔哩)该软件可以轻松地帮助...
外挂法子!aa poker辅助... 外挂法子!aa poker辅助,德普辅助器怎么用-本来存在有辅助插件(哔哩哔哩)1、aa poker...
外挂窍要!智星菠萝有挂吗,so... 外挂窍要!智星菠萝有挂吗,sohoo poker辅助-都是是有辅助技巧(哔哩哔哩)1、游戏颠覆性的策...
外挂指南!werplan免费挂... 外挂指南!werplan免费挂下载,哈糖大菠萝怎么开挂-果然是真的有辅助插件(哔哩哔哩)外挂指南!w...
外挂技法!悦扑克脚本,德州真人... 外挂技法!悦扑克脚本,德州真人透视脚本-好像存在有辅助方法(哔哩哔哩)1、德州真人透视脚本辅助器安装...