网络最短路径问题的研究与应用

发布时间：2017-11-10 00:00

  本文关键词：网络最短路径问题的研究与应用

  更多相关文章： 最短路径 Bellman-Ford算法 Floyd算法 改进算法 随机网络

【摘要】：最短路径问题是图论和网络优化理论研究的主要问题,用于求解网络中任意两点之间的最短路径。随着科技的发展,最短路径问题在计算机科学、地理信息科学、通信与军事运筹学等领域发挥越来越大的作用。因此,研究最短路径问题意义重大。首先,通过分析Bellman-Ford算法,针对其求解最短路长重复计算量大,寻找最短路径繁琐的问题,本文提出Ford算法的改进算法。改进算法通过引入路权数组有效降低了算法的时间复杂度,同时借助前点标号数组增强了寻路直观性。编写MATLAB程序,并在大型随机网络中仿真实验,结果显示Ford算法的改进算法更为有效。其次,对Floyd算法进行深入研究,通过引进迭代矩阵和下标标注法对其进行改进。Floyd改进算法提高了计算最短路长的效率,简化了寻找最短路径的步骤。给出算法复杂度、可行性分析和具体实例,并用Floyd改进算法与原算法计算大型网络最短路,理论分析和仿真结果都说明了改进算法的准确性和高效性。再次,本文提出用三个值标记一个节点的拓扑排序法的修正算法,修正算法通过增加前点标号改善了拓扑排序法求解最短路径繁琐的问题,通过只更新与出弧相连节点的标记,简化了计算量,提高了计算效率。最后,简单介绍最短路径问题在通信中的应用及其推广应用。
【学位授予单位】：南京邮电大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5

【相似文献】

中国期刊全文数据库 前10条

1 徐翠霞;;无环网络中的最短路径问题研究[J];科技广场;2007年03期

2 校景中;肖丽;;最短路径问题的优化算法研究[J];西南民族大学学报(自然科学版);2012年03期

3 张森;;改进蚁群算法求解最短路径问题[J];电子世界;2013年16期

4 张涛;陈忠;吕一兵;;求解最短路径问题的一种改进的人工蜂群算法[J];青海师范大学学报(自然科学版);2013年01期

5 余金山;;最短路径问题的解答图算法[J];华侨大学学报;1984年02期

6 柴登峰,张登荣;前N条最短路径问题的算法及应用[J];浙江大学学报(工学版);2002年05期

7 毕亚军;王晓威;邓凤茹;;网络图任意两点间最短路径问题的计算机实现[J];科技资讯;2006年31期

8 冯震;刘佳;李靖;曹延飞;;复杂网络中最短路径问题的求解算法研究[J];自动化技术与应用;2010年03期

9 伍建华,祁文青,晏伯武;单汇最短路径问题的一种算法[J];黄石高等专科学校学报;2001年02期

10 莫忠息;;网络中含有负圈的最短路径问题[J];武汉大学学报(自然科学版);1993年05期

中国重要会议论文全文数据库 前4条

1 崔岚;阮秋琦;;结点有拥塞的动态最短路径问题的算法研究[A];第十二届全国信号处理学术年会（CCSP-2005）论文集[C];2005年

2 刘翔;袁俊江;;改进遗传算法在不确定性最短路径问题的应用[A];第六届中国不确定系统年会论文集[C];2008年

3 王海梅;周献中;;直线优化A*算法在最短路径问题中的高效实现[A];全国第19届计算机技术与应用（CACIS）学术会议论文集（下册）[C];2008年

4 易正俊;黄华;张业亭;;模糊最短路径问题及标号法的实现[A];第五届中国不确定系统年会论文集[C];2007年

中国重要报纸全文数据库 前1条

1 于刚;走最近的路还是走最快的路？[N];中国国防报;2006年

中国博士学位论文全文数据库 前3条

1 俞峰;复杂动态随机网络最短路径问题研究[D];浙江大学;2009年

2 张钟;大规模图上的最短路径问题研究[D];中国科学技术大学;2014年

3 李杰;邻域可视性相关的路径规划问题研究[D];中国科学技术大学;2011年

中国硕士学位论文全文数据库 前10条

1 蒋腾飞;网络最短路径问题与应用研究[D];南京邮电大学;2013年

2 朱学智;基于遗传算法的最短路径问题研究[D];中国科学技术大学;2015年

3 梁娟;网络最短路径问题的研究与应用[D];南京邮电大学;2015年

4 邱钊;K最短路径算法及其应用研究[D];电子科技大学;2014年

5 刘佳;复杂网络中最短路径问题的优化算法研究[D];太原科技大学;2007年

6 王东旭;基于KEGG的代谢通路最短路径问题的研究[D];哈尔滨工业大学;2007年

7 吴虎发;蚁群优化算法在求解最短路径问题中的研究与应用[D];安徽大学;2012年

8 崔树林;求解不确定马尔克夫决策问题[D];吉林大学;2006年

9 方志斌;蚁群算法及其在路径优化问题中的研究[D];东华理工大学;2012年

10 平晓慧;最短路径问题的并行算法研究[D];大连理工大学;2006年

，

本文编号：1164133