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

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

相关内容

热门资讯

7分钟介绍!金州水鱼辅助工具,... 7分钟介绍!金州水鱼辅助工具,德州辅助(详细透视辅助神器教程)这是由厦门游乐互动科技有限公司精心打造...
五分钟透明!大头十三张有没有外... 五分钟透明!大头十三张有没有外挂,约局吧辅助工具获取方法(详细透视辅助app教程);致您一封信;亲爱...
四分钟攻略!全民比鸡是不是有外... 四分钟攻略!全民比鸡是不是有外挂,微扑克ai软件(详细透视辅助工具教程) 科技详细教程;757446...
五分钟透明!闲逸手机麻将有挂的... 1、五分钟透明!闲逸手机麻将有挂的么,德扑ai智能机器人平台安装(详细透视辅助脚本教程)(UU po...
2分钟总结!八仙竞技馆杭州麻将... 1、2分钟总结!八仙竞技馆杭州麻将攻略,wpk线上德州俱乐部(详细透视辅助脚本教程);详细教程。2、...
两分钟教学!天天闲来麻将有挂吗... WePoker透视辅助工具核心要点解析‌,两分钟教学!天天闲来麻将有挂吗,红龙扑克真假(详细透视辅助...
五分钟技巧!中至麻将打炸有挂的... 五分钟技巧!中至麻将打炸有挂的吗,nzt德州辅助软件基本了解(详细透视辅助脚本教程)1、很好的工具软...
四分钟介绍!jj麻将小程序修改... 四分钟介绍!jj麻将小程序修改器,微扑克专用辅助器(详细透视辅助软件教程)准备好在jj麻将小程序修改...
一分钟辅助挂!小闲巴渝棋牌取胜... 一分钟辅助挂!小闲巴渝棋牌取胜,wpk俱乐部24小时(详细透视辅助挂教程)是一款可以让一直输的玩家,...
5分钟透明!边锋干瞪眼辅助器使... 1、5分钟透明!边锋干瞪眼辅助器使用教程,微扑克wpk辅助存在(详细透视辅助神器教程)。2、边锋干瞪...