Python中如何实现Dijkstra算法_最短路径算法详解

无名

2025-06-19 377

在Python中实现Dijkstra 算法是解决最短路径问题的经典方法之一。Dijkstra算法广泛应用于图论、网络路由、地图导航等领域，它可以帮助我们在加权图中找到从起点到其他所有节点的最短路径。详细讲解如何使用Python来实现Dijkstra算法，并附上代码示例，帮助你快速掌握这一重要算法。

Dijkstra算法原理

Dijkstra算法通过贪心策略，逐步确定从起始节点到各个节点的最短路径。具体流程是：初始化起点距离为0，其他节点距离为无穷大；然后不断选择当前距离最小且未访问的节点，更新其邻居节点的距离，直到所有节点都被访问。算法保证了每次选中的节点都是当前未确定最短路径中距离最小的。

Python实现Dijkstra算法的步骤

实现Dijkstra算法，通常需要以下几个步骤：

图的表示
可以使用邻接矩阵或邻接表。这里采用邻接表，使用字典嵌套字典的形式表示图，键为节点，值为邻居及对应权重。
初始化数据结构
需要一个字典保存各节点的最短距离，初始时起点为0，其余为无穷大；使用集合或优先队列（heapq）来管理待访问节点。
更新距离和选择节点
使用优先队列提取当前距离最小的节点，遍历其邻居，若通过该节点路径更短，则更新邻居距离。
终止条件
当所有节点被访问或优先队列为空时结束。

Python代码示例

python

复制编辑

import heapq

def dijkstra(graph, start):
    # 初始化最短距离字典
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    # 优先队列初始化，存储（距离，节点）
    priority_queue = [(0, start)]
    
    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_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(priority_queue, (distance, neighbor))
    
    return distances

# 示例图的邻接表表示
graph = {
    'A': {'B': 5, 'C': 1},
    'B': {'A': 5, 'C': 2, 'D': 1},
    'C': {'A': 1, 'B': 2, 'D': 4, 'E': 8},
    'D': {'B': 1, 'C': 4, 'E': 3, 'F': 6},
    'E': {'C': 8, 'D': 3},
    'F': {'D': 6}
}

start_node = 'A'
shortest_distances = dijkstra(graph, start_node)
print(shortest_distances)

运行结果将输出从起点A到其他节点的最短路径距离。