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

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

相关内容

热门资讯

程序员教你!德州局怎么透视,p... 程序员教你!德州局怎么透视,poker辅助器免费安装,总是是真的有挂(的确有挂)1)有没有挂:进一步...
热点推荐!wpk私人辅助,po... 热点推荐!wpk私人辅助,pokemmo手机版脚本免费,切实是有挂(有挂讲解)辅助器是一种具有地方特...
总算了解!wepoker辅助器... 总算了解!wepoker辅助器安装包,wepoker辅助器安装包,其实是真的有挂(揭秘有挂)1、玩家...
发现玩家!wejoker私人辅... 发现玩家!wejoker私人辅助软件,aapoker插件,果然是真的有挂(有挂秘笈)在进入软件靠谱后...
热门推荐!wepoker轻量版... 热门推荐!wepoker轻量版有透视吗,德普之星有透视辅助吗,其实是有挂(有挂方略)一、游戏安装教程...
发现玩家!wepoker怎么挂... 发现玩家!wepoker怎么挂底牌,wepoker智能辅助插件,确实是有挂(有挂助手)小薇(辅助器软...
查到实测!wepoker私人定... 查到实测!wepoker私人定制透视,wepoker插件功能辅助器,切实是真的有挂(有挂方略)是不是...
科普分享!拱趴大菠萝十三水作弊... 科普分享!拱趴大菠萝十三水作弊,wepoker是不是有人用挂,其实真的是有挂(证实有挂)1、让任何用...
分享实测!wpk刷入池率脚本,... 分享实测!wpk刷入池率脚本,wepoker破解器,本来真的有挂(有挂教学)1、操作简单,无需手机版...
我来教教大家!德州辅助工具到底... 我来教教大家!德州辅助工具到底怎么样,智星德州辅助译码插件靠谱吗,总是是真的有挂(有挂分析)1、这是...