Dijkstra 算法

在边权非负的图上，求起点到其余各点最短路径的经典算法。

Dijkstra 算法由荷兰学者 Edsger Dijkstra 于 1956 年构想、1959 年发表，用来在边权（通行代价）非负的图上求单源最短路。做法是记下每个节点当前已知的最短距离，每次取出距离最小、还没确定的节点，用它更新邻居。它保证找到最优解，用二叉堆实现时复杂度约为 O((V+E)logV)，V、E 分别是节点数和边数。A* 是它的推广：多加一个「离终点还有多远」的估计（启发函数），优先朝目标方向搜，展开的节点更少。机器人导航里，栅格地图的每个格子是节点，代价地图的值是边权，Nav2 默认的 NavFn 规划器可选 Dijkstra 或 A* 扩展。

例子三个点 A、B、C：A→B 代价 1，B→C 代价 2，A→C 直连代价 4。算法先确定 B（距离 1），再经 B 把 C 的距离从 4 更新为 3，最终最短路是 A→B→C。

也叫

迪杰斯特拉算法、狄克斯特拉算法

相关

A* 算法、路径规划、代价地图、全局规划与局部规划、混合 A*

来源

Wikipedia: Dijkstra's algorithm
Nav2 Docs: NavFn Planner（wavefront Dijkstra or A*）