迪杰斯特拉-最短路径算法
迪丽瓦拉
2025-05-29 04:13:04
0次
迪杰斯特拉(Dijkstra)算法是基于动态规划实现的，他的主要功能是求出各节点到顶点的最短路径。
上图展示：
这是各节点连接图，其中A为顶点，求各节点到顶点的最短路径。
引进两个数组S和U。
S的作用是记录已求出最短路径的节点(以及相应的最短路径长度)，
U的作用是记录还未求出最短路径的节点(以及该节点到起点A的距离)。
第一步：创建S U数组，放入起点A到S
第二步：取最短的节点路径B放入S
第三步：将C放入后D节点的最短路径由 6 变化为 5
第四步：判断最短路径的节点放入S
第五步：判断最短路径的节点放入S
第六步：判断最短路径的节点放入S
至此各节点最短路径求出S={ A(0), B(3), C(4), D(5), E(9), F(9) }
动态规划的中心思想就是上一步永远都是最优解，通过各节点选择最短的路径到最后的结果必定为最优解。
下一篇：2023年跨境电商行业研究报告