本文主要是介绍迪杰斯特拉算法理解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
算法简介
迪杰斯特拉算法解决了从某个源点到其余各个顶点的最短路径问题,它最主要的特点是从起始点开始,采用贪心的策略,每次遍历到起始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止。
算法描述
1、令arcs
表示弧上的权值,若弧不存在,则设为无穷大;S
为已找到的从v
出发的终点的集合,初始状态为空集。那么,从v
出发到图上其余各顶点vi
可能达到的长度的初值为D = arcs[Locate Vex(G, vi)], vi ∈V
;
2、选择vj
,使得D [ j ] = Min{ D | vi ∈ V - S }
;
3、修改从v
出发的到集合V - S
中任一顶点vk
的最短路径长度。
其他
用直白不严谨的话来说就是:
从起点v0
出发,找到距离起点最近的点vk
,进而根据vk
到vk
的邻接点的距离,更新(取最小值,例如:v0—>v1权值为1,v0—>v2权值为4,v1—>v2权值为2,那么v0—>v1—>v2权值为3,小于v0—>v2的权值,所以更新v0到v2的距离)起点v0
到vk
的这些邻接点的距离;再在这些距离中找到最近的点,依次循环,直到到达终点。
这篇关于迪杰斯特拉算法理解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!