Dijkstra算法求单源最短路径问题 题目描述 给定一个带权有向图G=(V,E)，其中每条边e∈E都有一个非负权重w(e)≥0，以及一个源顶点s∈V。我们需要找到从源点s到图中所有其他顶点v∈V的最短路径。最短路径的长度是指路径上所有边的权重之和。目标是计算从s到每个顶点的最短距离（如果可达）。 解题过程 基本思想 Dijkstra算法的核心思想是贪心策略。它维护一个集合S，包含已经找到最短路径的顶点。算法反复从未被处理的顶点集合V-S中，选择一个距离源点s最近的顶点u，将其加入S，然后对u的所有出边进行松弛操作，更新s到其他顶点的距离估计。由于图中所有边的权重都是非负的，这个贪心选择策略能够保证每次加入S的顶点，其最短路径已经被确定。 数据结构准备 我们需要以下数据结构来辅助算法执行： dist[] ：一个数组， dist[v] 表示当前从源点s到顶点v的最短距离估计值。初始化时， dist[s] = 0 ，对于其他所有顶点v， dist[v] = ∞ （一个非常大的数，表示初始时不可达）。 visited[] （或集合S）：一个布尔数组，用于标记顶点是否已经被处理（即是否已加入集合S）。初始化时，所有顶点都未被访问（ visited[v] = false ）。 一个优先队列（最小堆）：用于高效地从未处理的顶点（V-S）中选出当前具有最小 dist 值的顶点。在初始化时，优先队列通常包含所有顶点及其 dist 值。 算法步骤详解 让我们一步步分解算法的执行过程： a. 初始化 设置源点s的 dist[s] = 0 。 设置其他所有顶点v的 dist[v] = ∞ 。 将所有顶点标记为未访问（ visited[v] = false ）。 将源点s（距离为0）加入优先队列。如果优先队列初始包含所有顶点，则需要更新s的距离。 b. 主循环 当优先队列不为空时，重复以下步骤： 选择最小距离顶点 ：从优先队列中取出当前 dist 值最小的顶点u。这个顶点u就是当前V-S集合中距离s最近的顶点。 标记为已访问 ：将顶点u标记为已访问（ visited[u] = true ），表示从s到u的最短路径已经找到。因为所有权重非负，不可能存在通过其他未访问顶点到达u的更短路径。 松弛操作 ：遍历顶点u的所有邻接顶点v（即存在边u→v）。对于每个邻接顶点v，如果v尚未被访问（ visited[v] == false ），则检查是否可以更新s到v的距离估计： 计算新的距离候选值： new_dist = dist[u] + w(u, v) ，其中 w(u, v) 是边(u, v)的权重。 如果 new_dist < dist[v] ，说明找到了一条从s经u到v的更短路径。于是进行更新： 设置 dist[v] = new_dist 。 在优先队列中更新顶点v的优先级（距离值）。在某些优先队列实现中，这可能是通过先删除再重新插入，或者使用支持减键操作的堆来实现。 c. 终止 当优先队列为空时，算法结束。此时， dist 数组中存储的就是从源点s到每个顶点的最短距离。对于任何顶点v，如果 dist[v] 仍然是∞，则表示从s不可达v。 关键点与示例 非负权重约束 ：Dijkstra算法要求图中所有边的权重必须非负。如果存在负权边，算法可能无法得到正确结果，因为贪心选择策略会失效（一个当前距离较大的顶点，可能通过负权边变得更小）。 时间复杂度 ：使用二叉堆作为优先队列时，时间复杂度为O((|V|+|E|) log |V|)。使用斐波那契堆可以优化到O(|V| log |V| + |E|)。 空间复杂度 ：主要为O(|V|)用于存储 dist 和 visited 数组，以及优先队列。 通过以上循序渐进的步骤，Dijkstra算法能够高效且正确地计算出带非负权重的有向图中，从单个源点到所有其他顶点的最短路径。