Dijkstra 算法的伪代码是什么？

伪代码将距离初始化为无穷大，前驱节点初始化为 nil，将源距离设为 0，并使用优先队列 H。它反复提取距离最小的顶点 u，松弛所有出边 (u,v)，如果找到更短的路径则更新 dist(v) 和 prev(v)，并减少 H 中 v 的键值。

适用条件

输入：图 $G = (V, E)$ ，有向或无向。
正边长 { $l_e$ : $e \in E$ }。
源顶点 $s \in V$ 。
输出：对于所有从 s 可达的 u，dist(u) 是从 s 到 u 的最短距离。

理解与推导

对所有 u in V，初始化 dist(u) = infinity 和 prev(u) = nil。
设置 dist(s) = 0。
创建优先队列 H，包含所有顶点，以 dist 值为键。
当 H 不为空时：从 H 中提取最小值 u。
对于每条边 (u,v) in E：如果 dist(v) > dist(u) + $l(u,v)$ ，则 dist(v) = dist(u) + $l(u,v)$ ，prev(v) = u，并 decreasekey(H, v)。

例子

视频显示了完整的伪代码：“procedure dijkstra(G,l,s)... H = makequeue(V)... while H is not empty: u = deletemin(H)... if dist(v) > dist(u) + $l(u,v)$ : dist(v) = dist(u) + $l(u,v)$ ...”

容易误解的地方

忘记将源距离初始化为 0。
假设算法适用于负边权（伪代码指定了正边长）。
在找到更短路径时未更新优先队列的键值。

观看对应讲解

YouTube迪杰斯特拉算法三分钟讲解

2:30 – 2:45原站看这一段 ↗

继续追问

答案依据视频资料生成并经过独立核验。若有疑问，请核对原视频或联系原作者。