这篇文章主要介绍“Dijkstra算法原理及C++怎么实现”的相关知识,小编通过实际案例向大家展示操作过程,操作方法简单快捷,实用性强,希望这篇“Dijkstra算法原理及C++怎么实现”文章能帮助大家解决问题。如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条,如何找到一条路径使得沿此路径上各边上的权值总和达到最小。单源最短路径问题是指对于给定的图G=(V,E),求源点v0到其它顶点vt的最短路径。Dijkstra算法用于计算一个节点到其他节点的最短路径。Dijkstra是一种按路径长度递增的顺序逐步产生最短路径的方法,是一种贪婪算法。Dijkstra算法的核心思想是首先求出长度最短的一条最短路径,再参照它求出长度次短的一条最短路径,依次类推,直到从源点v0到其它各顶点的最短路径全部求出为止。具体来说:图中所有顶点分成两组,第一组是已确定最短路径的顶点,初始只包含一个源点,记为集合S;第二组是尚未确定最短路径的顶点,记为集合U。按最短路径长度递增的顺序逐个把U中的顶点加到S中去,同时动态更新U集合中源点到各个顶点的最短距离,直至所有顶点都包括到S中。1.初始时,S集合只包含起点v0;U集合包含除v0外的其他顶点vt,且U中顶点的距离为起点v0到该顶点的距离。(U 中顶点vt的距离为(v0,vt)的长度,如果v0和vt不相邻,则vt的最短距离为∞)2.从U中选出距离最短的顶点vt′,并将顶点vt′加入到S中;同时,从U中移除顶点vt′。3.更新U中各个顶点vt到起点v0的距离以及最短路径中当前顶点的前驱顶点。之所以更新U中顶点的距离以及前驱顶点是由于上一步中确定了vt′是求出最短路径的顶点,从而可以利用vt′来更新U中其它顶点vt的距离,因为存在(v0,vt)的距离可能大于(v0,vt’)+(vt’,vt)距离的情况,从而也需要更新其前驱顶点4.重复步骤(2)和(3),直到遍历完所有顶点使用了部分C++11特性,注释丰富,读起来应该不会太困难!运行结果:D -> C: Length: 3 Paths: D -> C
D -> E: Length: 4 Paths: D -> E
D -> F: Length: 6 Paths: D -> E -> F
D -> G: Length: 12 Paths: D -> E -> G
D -> B: Length: 13 Paths: D -> C -> B
D -> A免费云主机域名: Length: 22 Paths: D -> E -> F -> A关于“Dijkstra算法原理及C++怎么实现”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识,可以关注百云主机行业资讯频道,小编每天都会为大家更新不同的知识点。
相关推荐: JavaScript滑动窗口的最大值问题怎么解决
这篇文章主要讲解了“JavaScript滑动窗口的最大值问题怎么解决”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“JavaScript滑动窗口的最大值问题怎么解决”吧!给定一个数组 nums 和滑动窗口的大小 …
免责声明:本站发布的图片视频文字,以转载和分享为主,文章观点不代表本站立场,本站不承担相关法律责任;如果涉及侵权请联系邮箱:360163164@qq.com举报,并提供相关证据,经查实将立刻删除涉嫌侵权内容。