导读:Dijkstra算法是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。Dijkstra算法主要特点是从起始点开始,采用贪心算法的策略,每次....

Dijkstra算法是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。Dijkstra算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止。
按路径长度递增次序产生算法:
把顶点集合V分成两组:
(1)S:已求出的顶点的集合(初始时只含有源点V0)
(2)V-S=T:尚未确定的顶点集合
将T中顶点按递增的次序加入到S中,保证:
(1)从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度
(2)每个顶点对应一个距离值
S中顶点:从V0到此顶点的长度
T中顶点:从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度
依据:可以证明V0到T中顶点Vk的,或是从V0到Vk的直接路径的权值;或是从V0经S中顶点到Vk的路径权值之和。
wwW.wenTIyI.coM版权声明:问题易所有作品(图文、音视频)均来源网络,版权归原创作者所有,与本站立场无关,如不慎侵犯了你的权益,请联系我们告知,我们将做删除处理!

