dijkstra算法实例

### Dijkstra算法实现及其解释

Dijkstra算法用于计算加权图中单源最短路径问题。该算法假设所有边权重均为非负数[^1]。

下面是一个Python版本的Dijkstra算法实现：

import heapq

def dijkstra(graph, start):
    # 初始化距离字典，默认值为无穷大
    distances = {node: float('infinity') for node in graph}
    # 起始节点的距离设为0
    distances[start] = 0
    
    # 使用优先队列来存储待处理节点 (distance, node)
    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`参数应该表示成邻接表形式的一个字典，其中键是顶点名称而值则是另一个字典，后者包含了指向其它顶点以及相应边上的权重的信息；`start`参数指定了要寻找从哪个起点出发到达其余各点之间的最短路径。

例如给定如下带权无向图:

| A | B | C |
|---|---|--|
| - | 7 | 9 |

可以构建这样的输入数据结构供函数调用:

example_graph = {
    'A': {'B': 7, 'C': 9},
    'B': {'A': 7},
    'C': {'A': 9}
}

print(dijkstra(example_graph, 'A'))

这段程序会输出由起始位置'A'至各个目的地之间所经过路程长度总和最少的结果集合。