### Python 实现基于 Dijkstra 算法的单源最短路径 以下是使用 Python 编写的基于 Dijkstra 算法的程序，用于计算从起点节点 1 到其他所有节点的最短距离。此代码支持多行输入，其中第一行为点数 `n` 和边数 `m` 的定义。 #### 输入说明 - 第一行为两个整数 `n` 和 `m`，分别表示图中的节点数量和边的数量。 - 接下来的 `m` 行每行包含三个整数 `u`, `v`, `w`，表示一条从节点 `u` 到节点 `v` 权重为 `w` 的有向边。 #### 输出说明 - 输出一行，包含从起始节点 1 到其余每个节点的最短距离。如果某个节点不可达，则输出 `-1`。 ```python import heapq def dijkstra(n, edges): graph = {i: [] for i in range(1, n + 1)} for u, v, w in edges: graph[u].append((v, w)) distances = [float('inf')] * (n + 1) distances[1] = 0 priority_queue = [(0, 1)] # (distance, node) 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]: distance = current_distance + weight if distance < distances[neighbor]: distances[neighbor] = distance heapq.heappush(priority_queue, (distance, neighbor)) result = [] for i in range(1, n + 1): if distances[i] == float('inf'): result.append(-1) else: result.append(distances[i]) return result # Input reading and processing input_data = input().split() n, m = int(input_data[0]), int(input_data[1]) edges = [] for _ in range(m): u, v, w = map(int, input().split()) edges.append((u, v, w)) result = dijkstra(n, edges) print(*result) ``` 上述代码实现了标准的 Dijkstra 算法，并通过优先队列优化了性能[^3]。它能够处理具有正权重边的加权图并找到从指定起点到所有其他节点的最短路径长度。 #### 关键点解释 - **图构建**：利用字典存储邻接表形式的图结构，便于快速访问任意节点的所有邻居及其对应的边权重。 - **初始化距离数组**：将所有节点的距离初始设为无穷大 (`float('inf')`)，仅设置起点距离为零。 - **优先队列**：采用最小堆来维护当前待扩展节点集合，每次选取离起点最近的一个未访问节点进行扩展操作。 - **松弛操作**：对于每一个新发现的更优路径更新目标节点的距离值，并将其加入候选列表供后续探索。 需要注意的是，该版本假设所有的边权重均为正值[^3]。如果有负权重存在则可能导致错误的结果或者陷入无限循环的情况发生。 问题