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

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

相关内容

热门资讯

开挂辅助工具"约局吧... 开挂辅助工具"约局吧德州可以透视吗"开挂(透视)辅助软件(存在有挂);无需打开直接搜索打开薇:136...
开挂辅助安装"wep... 您好:wepoker轻量版透视系统这款游戏可以开挂的,确实是有挂的,很多玩家在这款游戏中打牌都会发现...
开挂辅助软件"soh... 开挂辅助软件"sohoo poker辅助"开挂(透视)辅助平台(有挂存在);无需打开直接搜索薇:13...
开挂辅助平台"wep... 开挂辅助平台"wepoker手机版辅助"开挂(透视)辅助插件(有挂分享)1、下载安装好wepoker...
开挂辅助脚本"德州局... 开挂辅助脚本"德州局透视脚本"开挂(透视)辅助脚本(有挂功能)《详细加薇136704302咨询》游戏...
开挂辅助下载"德普之... 开挂辅助下载"德普之星透视辅助插件"开挂(透视)辅助安装(有挂教学)您好:德普之星透视辅助插件这款游...
开挂辅助下载"wep... 开挂辅助下载"wepokerplus万能挂"开挂(透视)辅助安装(有挂头条);无需打开直接搜索薇:1...
开挂辅助软件"来玩a... 开挂辅助软件"来玩app破解版"开挂(透视)辅助插件(有挂攻略);无需打开直接搜索薇:1367043...
开挂辅助安装"aap... 开挂辅助安装"aapoker俱乐部靠谱吗"开挂(透视)辅助神器(有挂分析) 了解更多开挂安装加(13...
开挂辅助平台"wpk... >>您好:wpk控制牌是真的吗确实是有挂的,很多玩家在这款wpk控制牌是真的吗游戏中打牌都会发现很多...