资源描述：
《求最短路径的新算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、CN4321258/TP计算机工程与科学2006年第28卷第2期ISSN10072130XCOMPUTERENGINEERING&SCIENCEVol128,No12,2006文章编号:10072130X(2006)02200832033求最短路径的新算法TheNewAlgorithmforFindingtheShortestPaths徐凤生XUFeng2sheng(德州学院计算机系,山东德州253023)(DepartmentofComputerScienceandTechnology,DezhouUniversity,Dez
2、hou253023,China)摘要:本文提出了一种求最短路径的新算法,并用C语言设计相应的程序验证了此算法。实验表明,该算法能高效地求出一个顶点到其它各顶点的所有最短路径。Abstract:Anewalgorithmforfindingtheshortestpathshasbeenputforwardinthispaper.Alltheshortestpathsfromonenodetoalltheothernodescanbederivedquicklybyusingthealgorithm.Thealgorithmisve
3、rifiedandimplementedbyarelevantCprogram.关键词:最短路径;Dijkstra算法;邻接矩阵Keywords:shortestpath;Dijkstraalgorithm;adjacentmatrix中图分类号:TP301.6文献标识码:A⋯,vm∈V,边(或弧)e1,e2,⋯,em∈E,其中vi-1、vi是ei的1引言结点,序列v0v1⋯vm称为连接v0到vm的路,记为v0v1⋯vm。路中边的数目称为该路的秩。ω01+ω12+⋯+ω(n-1)n最短路径问题是图论中研究的一个重要课题,它广泛称
4、为该路的长度。所有连接v0到vm的路中长度最小的路应用于交通、网络寻优等领域。最短路径问题要解决的就称为v0到vm的最短路径。是求加权图G=中两给定顶点之间的最短路通常的无向图和有向图可以看成是加权图的特例。[1]径。求最短路径的一个著名算法是Dijkstra算法,它可定义2给定简单加权图G=,V={v0,以求出图中从一个顶点到其它各顶点的最短路径的长度及v1,⋯,vn-1},称A=(aij)为图G的邻接矩阵,其中:一条最短路径。但是,该算法具有其局限性,不能求出从一ωij,若vi和vj之间有边相连个
5、顶点到其它各顶点的所有最短路径。1965年,EliOlin2aij=∞,若vi和vj之间无边相连ick和D.K.Smith等就求出所有最短路径这一问题进行了0,若i=j一些简单的探讨,但这些探讨过于简单且不完整。针对Di2ωij表示vi和vj之间边的权值。jkstra算法的局限性,孙强等人在文献[2]中给出了一种解求最短路径最著名的算法是Dijkstra算法,其基本思决方案,但其使用的数据结构形式较为复杂。文献[3]提出了一种新的解决方案,但其求解过程仍然十分繁琐。本文想是按路径长度递增的次序产生最短路径,可由下式给出:在对最短
6、路径问题进行了分析和探讨的基础上,提出了一D[i]=min{D[i],D[i]+ωji}种新的求从一个顶点到其它各顶点的所有最短路径的算Dijkstra算法具有其局限性,它只能求出一条最短路法。与文献[2,3]给出的算法相比,本文的算法具有数据结径,而不能求出所有最短路径。构形式简单、求解方便且比较直观等特点。3算法与实例2相关概念本文提出了一种求最短路径的新算法,其基本思想与定义1给定简单加权图G=,设v0,v1,Dijkstra算法一致,但它克服了Dijkstra算法的不足之处,3收稿日期:2004209201
7、;修订日期:2004210222基金项目:德州市科学技术攻关计划资助项目(040705)作者简介:徐凤生(1965),男,山东聊城人,教授,研究方向为数据挖掘、数据库技术、数据结构和算法。通讯地址:253023山东省德州市德州学院计算机系;Tel:(0534)8985635;E2mail:xfs@dzu.edu.cnAddress:DepartmentofComputerScienceandTechnology,DezhouUniversity,Dezhou,Shandong253023,P.R.China83能够快速地求出一个
8、顶点到其它各顶点的所有最短路径。表3修正P为了叙述方便,首先引入以下记号并作相应的约定。v0v1v2v3v4(1)向量D的每个分量D[i]表示当前所找到的从始v0021∞∞点v0到每个终点vi的最短路径的长度。v110112v22203∞(2)向量S的每个分量S
