2022年单源最短路径算法 2.pdf
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《2022年单源最短路径算法 2.pdf》由会员分享,可在线阅读,更多相关《2022年单源最短路径算法 2.pdf(4页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、设图 G=(V,E) 是一个有向图, 它的每一条边(U,V) 都有一个非负权W(U,V), 在 G中指定一个结点V0,要求从V0 到 G的每一个结点Vj 的最短路径找出来(或指出不存在)。由于源结点V0 是给定的,所谓称为单源最短路径。【Dijkstra算法思想】把所有结点分为两组。第一组:包含已确定最短路径的结点。第二组:包含尚未确定最短路径的结点。按最短路径长度递增的顺序把第二组的结点加到第一组中去,直到 V0 可达的所有结点都包含于第一组中。 在这个过程中, 总保持从V0 到第一组各结点的最短路径长度都不大于从V0 到第二组任何结点的路径长度。【单源最短路径算法实例】现有一张县城的城镇地
2、图,图中的顶点为城镇,无向边代表两个城镇间的连通关系,边上的权为公路造价,县城所在的城镇为v0。由于该县经济比较落后,因此公路建设只能从县城开始规划。规划的要求是所有可到达县城的城镇必须建设一条通往县城的汽车线路,该线路的工程总造价必须最少。【输入】第一行一个整数v,代表城镇数,县城编号为1。 第二行是一个整数e,表示有向边数。以下 e 行,每行为两个城镇编号和它们之间的公路造价。【输出】 v-1行,每行为两个城市的序号,表明这两个城市间建一条公路。【输入样例】6 10 1 2 10 1 5 19 1 6 21 2 3 5 2 4 6 2 6 11 3 4 6 4 5 18 4 6 14 5
3、6 33 【输出样例】原图从第 1 点出发的最短路径名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页,共 4 页 - - - - - - - - - 1 2 2 3 2 4 1 5 1 6 program dijkstra_example; const vmax=100; type path=record 此记录类型用于记录每一个结点与v0 的距离和其父结点 length:integer; pre:0.vmax; end; var w:array1.vmax,1.vmax of
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年单源最短路径算法 2022 年单源最短 路径 算法
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内