1 / 2
文档名称:

最短路径的算法思想.doc

格式:doc   大小:29KB   页数:2页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

最短路径的算法思想.doc

上传人:mh900965 2018/3/26 文件大小:29 KB

下载得到文件列表

最短路径的算法思想.doc

文档介绍

文档介绍:有两种算法可以实现,一种是迪杰斯特拉(Dijkstra)算法,一种是弗洛伊德(Floyd)算法。
迪杰斯特拉(Dijkstra)算法:
(给出一个出发点,可算出该出发点到所有其它点的最短距离还有具体路径)
算法过程:
一,用D[v]记录任一点v到出发点的最短距离,建立一S集合且为空,用以记录已找出最短距离的点。
二,扫描非S集中D[]值最小的节点D[w],也就是找出下一条最短路径,把节点w加入S集中。
三,更新所有非S集中的D[]值,看看是否可通过新加入的w点让其距离更短:if(D[w]+<w,v> < D[v]) then D[v]=D[w]+<w,v>;
四,跳转到(二)操作,循环(顶点数-1)次,依次找出所有顶点的最短路径。
算法理解:
先证明:下一条最短路径一定是经过S集中的顶点,或是直接到达出发点的。
也就是说下一条最短路径一定不经过S集外的顶点。
证明:如下图,v为出发点,假使w为下一条最短路径的顶点,则<v,u,w>一定小于<v,k>,否则称k为下一条最短路径,而不是w,所以<v,u,w> < <v,k> 则<v,u,w> < <v,k,w> 所以w一定通过S集中的顶点。
第一条最短路径当然是直到出发点且最短的那条,所以可以扫描初始化后的D[]直接找出最短那条,然后根据以上证明可得下一条最短路径一定是通过刚找出的那条的,由于下一条最短路径一定是通过S集的,所有不用每次都扫描所有的路径,所以只用更新有通过刚加入的顶点的路径D[]值(三操作)。再扫描出最短的D[]值,加入S集中(二操作),再更新所有D[]值,依次找出所有顶点。
弗洛伊德(Floyd)算法:
(算出所有每对顶点间的最短路径)
算法过程:
一,用D[v][w]记录每一对顶点的最短距离。
二,依次扫描每一个点,并以其为基点再遍历所有每一对顶点D[][]的值,看看是否可用过该基点让这对顶点间的距离更小。
算法理解:
最短距离有三种情况:
一,两点的直达距离最短。(如下图<v,x>)
二,两点间只

最近更新

针织用纱质量浅析 3页

采用精密距离测量在基坑平面位移中的应用 3页

《山中访友》教学设计 32页

连铸圆坯结晶器锥度优化设计研究 3页

辐照前处理木质纤维素的研究进展 3页

超声波淬火工艺在40Cr阶梯轴淬火中的应用 3页

论XBRL分类标准扩展——以石油天然气行业为例.. 3页

西非地区路网规划特点及公路建设发展研究 3页

行政事业单位内控测试评价、缺陷与优化探析 4页

表演动作猜成语素材 111页

苏54区块盒 8段储层气水分布特征及识别方法研.. 3页

2025年农村住房租赁市场租赁合同租赁权转让合.. 8页

职业企业家行为失范机理分析及其约束机制研究.. 3页

绩效考核在医院人力资源管理中的应用研究 3页

蒸发和降水的观测 57页

第六届粤港澳大湾区“粤菜师傅”技能大赛中式.. 13页

福建省旅游业发展前景SWOT分析 3页

硬质合金自动切菜机刀具设计及工艺优化 4页

石油销售企业竞争力的增强方式分析与研究 3页

苏霍姆林斯基给教师的100条建议之 9页

2025年鼓励孩子多读书的金句 7页

2025年鸡年农历九月宝宝取名技巧 4页

2025年高考选科选物理一定要选化学吗 4页

2025年高考毕业串场词 20页

苏卫单招校测2025试卷 9页

《黄河颂》33694省公开课一等奖全国示范课微课.. 29页

部编版九年级语文上册必背古诗文 8页

消毒小车策划书 4页

3D打印技术与虚拟现实的融合 26页

党建调研提纲 2页