Dijkstra 算法如何逐步更新距离？

适用条件

• 需要一个优先队列或列表来跟踪未访问节点及其当前最短距离。
• 图必须具有非负边权（伪代码中为正）。

理解与推导

1. 初始化距离：源 = 0，其他 = 无穷大。
2. 选择距离最小的未访问节点。
3. 对于所选节点的每个邻居，计算暂定距离：dist(current) + weight(edge)。
4. 如果暂定距离小于邻居当前记录的距离，则更新邻居的距离和前驱节点。
5. 将所选节点标记为已访问。
6. 重复直到所有节点都被访问或到达目标。

例子

在视频示例中，从 A（距离 0）开始，它将 B 更新为 4，C 更新为 2。然后选择 C（距离 2），将 B 更新为 3（通过 C，因为 $2+1 < 4$），D 更新为 6，E 更新为 7。

容易误解的地方

• 认为节点是按字母顺序或任意顺序访问的；它们是按照距源的递增最短距离顺序访问的。
• 假设一旦设置了距离，它就不会改变；每当找到更短的路径时，距离就会被更新（松弛）。

观看对应讲解

继续追问

• 使用斐波那契堆时 Dijkstra 算法的时间复杂度是多少？
• Dijkstra 算法的伪代码是什么？
• 为什么 Dijkstra 算法被认为是贪心算法？