1 / 8
文档名称:

几种常用的最短路径算法.doc

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

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

分享

预览

几种常用的最短路径算法.doc

上传人:wz_198614 2017/10/5 文件大小:20 KB

下载得到文件列表

几种常用的最短路径算法.doc

文档介绍

文档介绍:几种常用的最短路径算法
摘要:随着社会的发展,最短路径问题在现实生活中占据的地位越来越重要。求解这一类问题的方法有很多,包括Floyd算法、Dijkstra算法、Bellman-Ford算法、动态规划算法和智能优化算法。其中较为常用的是Floyd算法、Dijkstra算法和Bellman-Ford算法。本文将简单介绍这三种最短路径算法,通过比较各种方法的优劣使对其有更进一步的认识和学习。
关键字:最短路径;最短路径算法;Floyd算法;Dijkstra算法;Bellman-Ford算法随着计算机科学的发展,人们生产生活效率要求的提高,最短路径问题逐渐成为计算机科学、运筹学、地理信息科学等学科的一个研究热点。也正因为最短路径问题在实际生产生活中应用广泛,优化该算法和提高算法的求解效率具有重大的现实意义。

最短路径问题是指在一个赋权图的两个节点之间找出一条具有最小权的路径,这是图论的描述,也是图论中研究的一个重要问题。现实生活中我们可以看到这些最短路径问题的例子,公交车辆的最优行驶路线和旅游线路的选择等;军事领域中也有应用,作战部队的行军路线等问题就与寻找一个图的最短路径密切相关,因此对最短路径问题的深入研究和广泛应用具有重要意义和实用价值。
在线路优化问题中,如果优化指标与路程的相关性较强,而和其他因素相关性较弱时,即以最短路程为准则,则考虑转化为最短路径问题。比如军事行军线路选取时,假如从出发地到目的地之间有多种线路可以选取,
危险指数在预测概率相等时,就要考虑最短路径问题。

最短路径算法问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。算法具体的形式包括:
确定起点的最短路径问题- 即已知起始结点,求最短路径的问题。
确定终点的最短路径问题- 与确定起点的问题相反,该问题是已知终结结点,求最短路径的问题。在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
确定起点终点的最短路径问题- 即已知起点和终点,求两结点之间的最短路径。全局最短路径问题- 求图中所有的最短路径。


Floyd算法是解决任意两点间的最短路径的一种算法,可以正确处理有向图或负权的最短路径问题,同时也被用于计算有向图的传递闭包。Floyd算法的时间复杂度为O(N3),空间复杂度为O(N2)。


Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话,首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题,我们需要为这个目标重新做一个诠释。
从任意节点i到任意节点j的最短路径不外乎2种可能,1是直接从i到j,2是从i经过若干个节点k到j。所以,我们假设Dis(i,j)为节点u到节点v的最短路径的距离,对于每一个节点k,我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立,如果成立,证明从i到k再到j的路径比i直接到j的路径短,我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j),这样一来,当我们遍历完所有节点k,Dis(i,j)中记录的便是i到j

最近更新

仓库、隧道爆破施工的安全事故预案与仓库火灾.. 5页

粮食检验知识培训 68页

交通局实践科学发展观调研阶段总结与交通局本.. 16页

类文本阅读题型归纳总结 11页

云南省最新版保育员四级专业能力考试试题试卷.. 12页

云南省2020年小升初数学能力测试试题-附解析 4页

云南省2019-2020年度保育员理论考试试题试卷及.. 11页

云南省2018年保育员五级业务能力考试试题试卷.. 10页

“幼儿园大二班九月份区域活动计划”幼儿园工.. 3页

2021年一级建造师《机电工程管理与实务》试题.. 8页

管理提升案例之刀具全寿命 20页

管理信息系统案例分析手机销售系统分析与设计.. 24页

店面装修合同样本范文3篇 49页

工业园区厂房翻新协议3篇 52页

展览器材搬迁运输协议3篇 53页

基于STL容器的分布式计算框架优化策略-全面剖.. 26页

家电产品海运合同示范文本3篇 52页

乳杆菌在治疗儿童感染性疾病中的应用前景-全面.. 27页

如何明确岗位职责岗位分析资料 38页

气性坏疽外科手术策略-全面剖析 35页

认知神经科学-全面剖析 26页

外研版小学英语三年级上册期末复习课件 24页

2025年小学数学新课程培训心得体会 13页

2025年小学教师师德师风演讲稿优秀 3页

2025年小学教师个人总结参考(精选篇) 25页

2025年小学师德师风演讲稿怎么写 12页

笠翁对韵一东 10页

车辆维修完过后的协议 5页

2025年长春医学高等专科学校单招职业技能测试.. 75页

2025年辽宁省交通高等专科学校单招职业倾向性.. 73页