### 计算无向图中最短路径的Dijkstra算法 在Python中，可以使用Dijkstra算法来解决带权无向图中的最短路径问题。该算法通过维护一个距离数组和优先队列逐步更新节点间的最小权重路径[^1]。 以下是基于邻接矩阵表示法的一个简单实现： ```python import heapq def dijkstra(graph, start): n = len(graph) dist = [float('inf')] * n # 初始化所有节点的距离为无穷大 visited = [False] * n # 节点访问状态 dist[start] = 0 # 起始节点到自身的距离为0 heap = [(0, start)] # 使用堆保存当前最短路径候选者 while heap: current_dist, u = heapq.heappop(heap) # 取出当前最短路径的节点 if visited[u]: continue visited[u] = True for v, weight in enumerate(graph[u]): if weight > 0 and not visited[v]: # 如果存在边且未被访问过 alt = dist[u] + weight # 更新可能更短的路径 if alt < dist[v]: dist[v] = alt # 更新目标节点v的距离 heapq.heappush(heap, (dist[v], v)) # 将新发现的较短路径加入候选项 return dist # 示例：构建一个简单的无向加权图（邻接矩阵） graph = [ [0, 10, 20, 0, 0], [10, 0, 5, 1, 0], [20, 5, 0, 2, 8], [0, 1, 2, 0, 3], [0, 0, 8, 3, 0] ] start_node = 0 shortest_distances = dijkstra(graph, start_node) print(f"从节点 {start_node} 到其他各节点的最短距离:") for i, distance in enumerate(shortest_distances): print(f"{i}: {distance}") ``` 上述代码实现了Dijkstra算法并返回起始节点到其余所有节点的最短路径长度。其中`heapq`模块用于高效管理优先队列操作[^3]。 ### 关键概念解释 - **邻接矩阵**：用来描述图结构的一种方式，在本例中采用二维列表形式存储每一对顶点间是否存在连接及其对应的权重。 - **优先队列**：帮助快速找到下一个具有最小临时距离值的顶点以便扩展其邻居节点。 此方法适用于稠密型图场景；对于稀疏图，则推荐考虑Floyd-Warshall或其他优化版本以提高效率[^4]。