学习动机

Dijkstra 会逐步扩展一个顶点集合，其中每个顶点的最短距离都已确定。它总是先确定尚未确定的顶点中距离最近的一个，然后用它来优化（松弛）到其邻居的距离。

为什么要学习 Dijkstra？

• 应用广泛：GPS 路线规划、网络数据包路由，以及任何寻找最低成本路径的场景。
• 有效的贪心算法：这是一个清晰的例子，说明贪心选择可以有严格的最优性保证，前提是权重非负。
• 基础算法：它的松弛思想也会出现在 A* 和其他最短路径算法中。

重要提示：Dijkstra 假设不存在负权重。对于负权边，需要使用 Bellman-Ford，这是下一门课程的内容。