资源描述：
《关于最短路径问题的一种有效算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、系统工程与电子技术第22卷第11期SystemsEngineeringandElectronicsVol22,No112000文章编号:1001-506X(2000)11-0094-04关于最短路径问题的一种有效算法吴晓红中山学院计算机系,528402摘要经典的关于最短路径算法是基于图的搜索思想的。Dijkstra提出的单源点最短路径和所有顶点对之间的最短径算法就是较为成熟的经典算法。但人们在长期的使用过程中感到其算法结构过于复杂且效率较低。对Dijkstra最短路径算法进行了改进,提出了WY-Dijkst
2、ra算法。改进后的算法不实施Dijkstra算法的重复循环,而是作映射或链接处理,从而提高了效率。这一算法适合于复杂的智能系统的应用。主题词路径算法系统效率中图分类号:TP3016OnanEffectiveAlgorithmoftheShortestPathProblemWuXiaohongDepartmentofComputerofZhongshanCollege,528402AbstractTheclssicalalgorithmabouttheshortestpathisbasedonsearchingm
3、ethodofgraph.Thealgorithmoftheshortestpathofsinglesourceandamongallvertexpairs,whichissuggestedbyDijkstra,ismaturerclassicalalgorithm.Butitscomplexalgo-rithmstructureanditslowerefficiencyisknownbyusforalongtime.Inthispaper,theDijkstrasalgorithmofshortestpathproble
4、misimprovedandtheWY-Dijkstraalgorithmisgiven.ThenewalgorithmdoesnotcarryoutarecycleoftheDijkstrasalgorithm.TheWY-Dijstraalgorithmonlycarryoutmappingorlinkedlistandsohasraisedefficiency.Thisalgorithmcanbeappliedtoartificialintelligencesystem.KeywordsPathAlgorith
5、mSystemefficiency当前所找到的从始值V到每个顶点Vi的最短路径长度。1引言下面将分析Dijkstra算法。生产实践,运输管理以及工程建设的许多方面,诸如各(1)假设用带权的邻接矩阵cost来表示带权有向图,种工艺路线的安排,厂区及货场的布局,管道线网的铺设等cost[i,j]表示弧上的权值(ij,否则cost[i,j]问题,都与寻找一个图的最短路径问题密切相关[1]。50年=0)。若不存在,则置cost[i,j]为(在计算机上代末,Dijkstra提出了按路径长度不减次
6、序产生的最短路径可允许的最大值)。S为已找到从V出发的最短路径的顶点集的算法,虽然一直被人们采用,但算法低效率在结点多的情合,它的初始状态为空集。那么,从V出发到图上其余各顶点况下仍很突出。由于上述应用对时间要求不是非常迅速,Vi可能达到的最短路径长度的初值为Dijkstra算法仍有广泛的用途。dist[i]=cost[ORDINAL(V),i]ViV目前,最短路径算法在智能系统的代价驱动搜索、神经ORDINAL(V)表示顶点在有向网D中的序号。元网络等研究领域也越来越受到重视。在这些研究中,不仅(2)选择Vj,使得要寻
7、找一个图的最短路径,而且要不断生成新图,不断寻找dist[j]=min{dist[i]
8、ViV-S}[2]V新的最短路径。这个过程,效率问题显得尤为重要。本文j就是当前求得的一条从V出发的最短路径的顶点。令保留Dijkstra不减次序基本思想,提出改进算法,旨在提高效S=S{j}率。(3)修改从V出发到集合V-S上任一顶点Vk可达到的最短路径长度。如果2Dijkstra算法分析dist[j]+cost[j,k]9、:1999-10-06修订日期:2000-04-20作者简介:吴晓红(1960-),女,副教授,学士,主要研究方向为计算机算法理论,神经网络理论与应用,计算机管理信息系统。第11期关于最短路径问题的一种有效算法95dist[k]=dist[j]+cost[j,k](n-1)n,而T
