Dijkstra 算法是什么？导航软件找最短路线的经典方法

Dijkstra 算法（迪杰斯特拉算法）是寻找图中单源最短路径的经典算法，由荷兰计算机科学家艾兹赫尔·戴克斯特拉（Edsger W. Dijkstra）在 1956 年提出，并在 1959 年发表。“单源最短路径”是指：从一个起点出发，求它到图中其他所有点的最短路径。它以简洁和高效著称，在计算机科学和运筹学中有着广泛的应用。据说戴克斯特拉是在一家咖啡馆里，花了大约二十分钟想出了这个算法。

核心思想

可以把图想象成一张地图：点是城市，边是城市之间的道路，边上的数字是道路的长度。Dijkstra 算法的核心思想是从起点出发，像水波一样逐步向外扩展：

一开始，起点到自己的距离是 0，到其他所有城市的距离都暂时记为无穷大。每一轮，从还没有确定最短距离的城市中，挑出当前距离起点最近的那一个，此时它的最短距离就确定了。然后，看看从这个城市出发能到达的邻居城市：如果经过它到达某个邻居，比之前记录的距离更短，就更新那个邻居的距离。重复这个过程，直到所有城市的最短距离都确定下来。

它属于贪心算法：每一步都选择当前看起来最好的选择。之所以能保证结果正确，是因为边的长度都不是负数：既然当前这个城市是所有未确定城市中最近的，就不可能再通过别的路径绕回来，找到更短的距离。

效率和限制

朴素的实现方式，每一轮都要扫描所有城市找出最近的那个，时间复杂度和点数的平方成正比。使用优先队列（比如二叉堆）来快速找出最近的城市，可以显著提高效率，适合处理大规模的稀疏图。它的主要限制是不能处理负权边：如果某条道路的长度是负数，比如代表某种补贴或收益，贪心的选择就可能出错，这时需要用 Bellman-Ford 等其他算法。

应用

地图导航软件计算两地之间的最短或最快路线；网络中的路由协议，比如 OSPF，计算数据包的最优转发路径；游戏中角色的寻路；物流配送的路径规划。实际的导航系统往往在它的基础上做了大量优化，比如 A* 算法加入了对目标方向的估计，能更快地找到路线。