最短路径问题

Dijkstra算法详解(会考)

算法背景

Dijkstra算法是解决单源最短路径问题的经典算法，适用于带非负边权的有向/无向图。其核心思想是贪心策略，通过逐步确定从源点到各顶点的最短路径。

修正后的算法步骤（修正原图符号错误）

输入：

带权图 $G=(V,E,W)$ ，其中 $V$ 是顶点集， $E$ 是边集， $W(e) \geq 0$ 表示边权
源点 $s \in V$

输出：

$s$ 到所有顶点 $v \in V$ 的最短距离 $d(v)$ 及路径

1. 初始化：
   - 对每个顶点 v ∈ V：
     d(v) ← +∞          // 初始距离设为无穷大
     prev(v) ← null      // 前驱顶点指针
   - d(s) ← 0            // 源点距离为0
   - 创建优先队列 Q，按 d(v) 排序，初始包含所有顶点

2. while Q 不为空：
   a. 从 Q 中取出 d(u) 最小的顶点 u（永久标号）
   b. 对 u 的每个邻接顶点 v：
     if d(v) > d(u) + W(u,v)：
       d(v) ← d(u) + W(u,v)  // 更新距离
       prev(v) ← u           // 记录路径
       Q 中调整 v 的优先级

Flowershow Cloud