最短路径算法Python

### Python 实现 Dijkstra 算法

Dijkstra算法用于求解加权图中的单源最短路径问题，适用于不含负权重的边。该算法通过维护一个距离表`dist`记录起点到各节点的距离，并不断更新这个表格直到找到最优解。

下面是一个基于Python编写的简单版本的Dijkstra算法实现：

import sys
import heapq

def dijkstra(graph, start):
    n = len(graph)
    dist = [sys.maxsize] * n  # 初始化所有节点的距离为无穷大
    dist[start] = 0           # 起始节点的距离设为0
    visited = set()            # 记录已访问过的节点集合
    
    pq = [(0, start)]          # 创建优先级队列，存储(当前距离, 当前节点)

    while pq:
        current_dist, u = heapq.heappop(pq)  # 取出最小堆顶元素
        
        if u in visited:                      # 如果已经访问过，则跳过
            continue
            
        visited.add(u)                        # 将当前节点标记为已访问
        
        for v, weight in graph[u]:
            if v not in visited and (new_dist := current_dist + weight) < dist[v]:
                dist[v] = new_dist             # 更新更短的距离
                heapq.heappush(pq, (new_dist, v))  # 加入新的候选节点
                
    return dist                                # 返回最终的结果列表

此代码片段定义了一个名为`dijkstra()`函数接收两个参数：一个是表示图形结构的数据结构`graph`；另一个是指定起始位置的整数索引`start`。这里采用邻接表的形式构建输入图表数据，在实际应用中可以根据具体需求调整这部分逻辑[^1]。

对于上述给出的例子来说，如果想要测试这段程序的效果，可以通过构造一个简单的例子来进行验证:

if __name__ == "__main__":
    # 构建一个简单的无向有权图作为测试案例
    test_graph = [
      [(1, 7), (2, 9)],       # Node 0 connects to node 1 with cost 7 and node 2 with cost 9.
      [(0, 7), (2, 10), (3, 15)],
      [(0, 9), (1, 10), (3, 11), (4, 2)],
      [(1, 15), (2, 11), (4, 6), (5, 9)],
      [(2, 2), (3, 6), (5, 4)],
      [(3, 9), (4, 4)]
    ]
    
    result = dijkstra(test_graph, 0)
    print(f"The shortest path from vertex 0 are {result}")

执行上面的脚本将会输出从顶点0出发到达其余各个顶点之间的最短路径长度[^5]。