dijkstra(迪杰斯特拉)算法详解

概念：是一种用于在带权图中计算单源最短路径的经典算法，由荷兰计算机科学家艾兹赫尔·戴克斯特拉于1956年提出。该算法采用贪心策略，逐步确定从源点到其他所有顶点的最短路径，适用于边权非负的有向图或无向图。‌‌

1.1  规则

从起始点开始，采用贪心算法的策略，每次遍历到离起始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

1.2 实例

 问题：计算从1出发到5最短路径

由图可知，1->2的权值为7,1->3的权值为9,1->6的权值为14,2->4的权值为15，2->3的权值为10,  3->4的权值为11,3->6的权值为2,4->5的权值为6 ，6->5的权值为9

（1）初始化，假设各个节点到1都有连线，无法直连的则标注为∞。所以2的前缀为1，权值为7；3的前缀为1，权值为9；6的前缀为1，权值为14,4 的前缀为1，权值为∞；5的前缀为1，权值为∞

（2）经过比较权值，可以确定1->2（1,2）的最短路径权值为7，选择2作为下一个节点，前缀为1，权值为7,。从2出发，可以到达3和4，但经过比较，到达3的权值为17<9,所以确定1->3(1,3)的最短路径权值为9，前缀为1；此时1->4（1,2,4）的前缀改为2，权值为22

（3）上一步确定1->3的最短路径，此时从3出发，可以到达4和6.则1->6的权值为11<14,此时确定1->6（1,3,6）的最短路径，前缀为3，权值和为11.1->4（1,3,4）的权值为20<22，确定1->4（1,3,4）的最短路径，前缀为3。

（4）上一步确定1->4的最短路径和1->6的最短路径。此时从4出发，可到达并未确定的点为5，权值为26.从6出发到达5的权值为20.可知到达5的最短路径为1->5(1,3,6,5)，前缀为6.

（5）最后，可得知从1到达各个点的最短路径为

1.3 代码实现：

import heapq

def dijkstra(graph, start):
    # 初始化距离字典：所有节点距离设为无穷大，起点设为0
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    
    # 记录每个节点的前驱节点（用于重建路径）
    predecessors = {node: None for node in graph}
    
    # 使用优先队列（最小堆），存储(距离, 节点)
    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
                predecessors[neighbor] = current_node  # 记录路径
                heapq.heappush(priority_queue, (distance, neighbor))
    
    return distances, predecessors

def get_shortest_path(predecessors, start, end):
    """根据前驱节点字典重建从起点到终点的路径"""
    path = []
    current = end
    
    # 从终点回溯到起点
    while current is not None:
        path.append(current)
        current = predecessors[current]
    
    # 反转路径（起点->终点）
    path.reverse()
    
    # 检查是否找到有效路径
    if path[0] != start:
        return None  # 起点与终点不连通
    
    return path

# 测试用例
if __name__ == "__main__":
    # 使用邻接表表示图（字典的字典）
    graph = {
        'A': {'B': 1, 'C': 4},
        'B': {'A': 1, 'C': 2, 'D': 5},
        'C': {'A': 4, 'B': 2, 'D': 1},
        'D': {'B': 5, 'C': 1}
    }
    
    start_node = 'A'
    distances, predecessors = dijkstra(graph, start_node)
    
    
    print("\n从节点 {start_node} 到各节点的最短路径:")
    for node in graph:
        if node == start_node:
            continue
        
        path = get_shortest_path(predecessors, start_node, node)
        if path:
            path_str = " → ".join(path)
            print(f"{start_node} → {node}: {path_str} (距离: {distances[node]})")
        else:
            print(f"{start_node} → {node}: 路径不存在")

代码运行效果图：