带权图的图搜索算法——Dijkstra算法_二维矩阵dijstra最优路径搜索

作者：很楠不爱3 | 2024-06-09 19:39:16

踩

二维矩阵dijstra最优路径搜索

图搜索算法的基本流程如下：

Dijkstra算法是从一个顶点到其余各顶点的最短路径算法。

Dijkstra算法的代价函数f(n)定义为：f(n)=g(n)，其中g(n)表示从起点到当前点的移动代价。

计算左上角起点到右下角终点的最短路径，箭头上的数值表示两个节点间的距离。

首先扩展第一个节点，计算其余节点与第一个节点的距离，用深蓝色标出已经扩展的节点，未扩展的节点仍用绿色标出，其中圆中的数值表示该节点的代价函数，字母则表示该节点没有直接到达此时已扩展节点的路径。从未扩展的节点(绿色节点)中选择代价函数最小的节点进行拓展，并更新其余节点的代价函数，如下图：

重复进行上面的步骤，直到所有节点都已扩展。

最后标出起点到终点的最短路径

将Dijkstra算法应用到二维地图路径规划中，如下图，可以看到Dijkstra算法能够得到最优路径

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/695535