无向图的单源最短路径问题（Dijkstra算法） 题目描述 给定一个无向图，图中每条边有一个非负权值（即距离或成本），并指定一个起点（源点）。要求找出从源点到图中所有其他顶点的最短路径长度。如果存在无法到达的顶点，则其最短路径长度为无穷大。 解题过程 Dijkstra算法是解决非负权图单源最短路径问题的经典算法。其核心思想是贪心策略：每次从未确定最短路径的顶点中选取距离源点最近的顶点，并更新其邻居的距离。以下是详细步骤： 初始化 创建一个数组 dist ，用于记录源点到每个顶点的当前最短距离估计。初始时， dist[源点] = 0 ，其他顶点设为无穷大（表示尚未到达）。 创建一个优先队列（最小堆），用于高效获取当前距离最小的顶点。初始时将源点及其距离 0 入队。 创建一个集合（或布尔数组） visited ，标记顶点是否已确定最短路径。 主循环 当优先队列不为空时，重复以下步骤： 提取最小距离顶点 ：从队列中取出当前距离源点最近的顶点 u ，及其距离 d 。 跳过已处理顶点 ：如果 u 已被标记为 visited ，说明其最短路径已确定，直接跳过。 标记为已处理 ：将 u 标记为 visited ，此时 dist[u] 即为最终最短距离。 松弛操作 ：遍历 u 的所有邻居顶点 v ，检查是否存在更短路径： 若 dist[u] + weight(u, v) < dist[v] ，则更新 dist[v] = dist[u] + weight(u, v) ，并将 v 及其新距离加入优先队列。 终止条件 当所有顶点均被标记为 visited （或优先队列为空）时，算法结束。此时 dist 数组存储的就是源点到所有顶点的最短距离。 关键点说明 贪心正确性 ：由于边权非负，每次选择最小距离顶点时，其当前距离不可能再被其他路径刷新。 时间复杂度 ：使用二叉堆实现的优先队列，时间为 O((V+E) log V)，其中 V 为顶点数，E 为边数。 适用限制 ：不适用于包含负权边的图（可能产生错误结果）。 示例 假设无向图包含顶点 {A, B, C}，边权为 A-B:2, A-C:4, B-C:1，源点为 A： 初始化：dist[ A]=0, dist[ B]=∞, dist[ C ]=∞。 处理 A：更新 B=2, C=4。 处理 B（当前最小）：通过 B 更新 C 为 2+1=3（优于原来的 4）。 处理 C：无需更新。 结果：dist[ A]=0, dist[ B]=2, dist[ C ]=3。