在图论中，Dijkstra 算法的目的是什么？

适用条件

• 图必须是加权的。
• 图可以是有向的或无向的，尽管视频主要在加权有向图上演示。

理解与推导

1. 识别起始节点（源）。
2. 将所有其他节点的初始距离设为无穷大，除源节点设为 0。
3. 选择当前距离最小的未访问节点。
4. 如果通过当前节点找到更短的路径，则更新其邻居的距离。
5. 将当前节点标记为已访问。
6. 重复直到所有节点都被访问。

例子

视频指出：“Dijkstra 算法找到一个节点到每个其他节点的最短距离。”并将其与产生最小生成树的 Prim 和 Kruskal 算法进行对比。

容易误解的地方

• 将 Dijkstra 算法与 Prim 或 Kruskal 算法混淆；Dijkstra 查找从源出发的最短路径，而不是最小生成树。
• 假设 Dijkstra 适用于具有负边权的图（伪代码指定了正边长）。

观看对应讲解

继续追问

• Dijkstra 算法如何逐步更新距离？
• 使用斐波那契堆时 Dijkstra 算法的时间复杂度是多少？
• Dijkstra 算法的伪代码是什么？