基于Dijkstra的最短路径改进算法

《基于Dijkstra的最短路径改进算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第!$卷第"期湖北汽车工业学院学报)*+,!$-*,""009年/月Q;E-A.<;?REN=(5E,;B;,(H=@ADE+,-(=+@A+,(,E,=QEA,"009基于!"#$%&’(的最短路径改进算法罗理!王锋!昆明理工大学信息工程与自动化学院#云南昆明/&00&$"摘要!针对如何利用’()*+,-.算法来高效地查找图中任意两结点之间的最短路径这一问题#提出了"种优化方法%其一是应用图中各结点的出入度来简化查找任意两结点之间的最短路径’其二是利用已求出的两点之间的最短路径来快速获得其他结点之间的最短路径$关键词!最短路径’最短路径算法’’()*+,-.算法’出入度中图分类号!12

2、30$4/文献标识码!5文章编号!$0067&863!"009"0"!00""!08!"#$%&’()*+%$,-."%/0.%$-12-34-.562’7%89,:;2-$6"#$"%#&’!()*!(!:;<<=>=;?@A?;-B.,(;ACA>(A==-(A>.AD5E,;B.,(;A#FEAB(A>GA(H=-+(,I;?JK(=AK=.AD1=KLA;<;>I#FEAB(A>/&00&#:L(A."<=2-$6>-%5(B(A>.,,L=M-;N<=B;?L;O,;B;-==??=K,(H=

3、=+(A>-.MLNI,L=.<>;-(,LB;?’()*+,-.#,L=,O;;M,(B(P=DB=,L;D+O=-=N-;E>L,?;-O.-D#OL(KLO=-=.MM;E,!(AD=>-==;?A;D=+(A,L=>-.ML,;+(BM<(?I,L=+=.-KL;?,L=+L;-,=+,M.,LN=,O==A.-N(,-.-I,O;A;D=+.ADB.*(A>E+=;?>.(A=D.<-=.DI,L=+L;-,=+,M.,LN=,O==A,O;A;D=+,;>.(A-.M(D,L=;,L=-A;D=+4?1@A%$(2%+L;

4、-,=+,M.,L’.<>;-(,LB;?,L=+L;-,=+,M.,L’.<>;-(,LB;?’()*+,-.’;E,!(AD=>-==随着社会的不断进步#最短路径算法在人们的是从固定的一个点到其他各点的最短路径问题$但日常生活显得越来越重要$比如%每天开车去上班#是在实际生活中往往要求解决的不只是固定一点应该选择哪条公路才能使自己到公司的费用最低&到其他点的最短路径#而是要求计算出任意两点之时间最少#这是最短路径的问题’在网络路由中#怎间的最短距离$针对这个问题#本文主要讨论了怎样选择最优的路由路径#这也是最短路径问题’在样利用’()*+,-.算法优化实现图中任意两点之间交通旅游&城

5、市规划以及电网架设中怎样使其耗费的最短路径问题$的资金最少#这还是最短路径问题$由此可见对最短路径问题的研究是非常有意义的$$基本思路最短路径这一重要问题早在"#世纪初就已经得到人们的高度重视#当时也有许多科学家研究这为了解决最短路径问题#首先应根据要求选取一重要问题的求解方法$但直到$%&%年荷兰计算一种量度标准$然后将!个输入排成这种量度标准机科学家’()*+,-.!迪杰斯特拉"才给出这一问题求要求的顺序#按照这种顺序一次输入一个量$如果解的基本思想#并给出了算法$后来这个算法就成这个输入和当前已经构成的在这种量度意义的部了众所周知的’()*+,-.算法#也成为了一代经典$分最优解加

6、在一起能产生一个可行解#则把此输入当时的’()*+,-.提出的这一算法主要解决的问题加到这部分最优解中#否则不加入$这种能够在某收稿日期!!""#!"$!%&作者简介!罗理!%’(!!"#男#湖南长沙人#硕士生#主要从事网络信息安全研究$第!!卷第"期罗理等,基于’()*+,-.的最短路径改进算法!!"!种量度意义下得到最优解的分级处理方法称为贪!(根据’()*+,-.算法思想!可以由图中结点的心算法"出入度信息来提高各点之间最短路径的查找速度&按照上面的思路!可以逐步地构造出这些最短"(在带权图中利用’()*+,-.算法找出部分结点路径"使用迄今已经生成的所有路径长度之和作之间的最短路

7、径后!若其他还没有找出最短路径的为一种量度!为了使这一量度达到最小!单独的每结点可以利用前面已找出的最短路径信息为自己一条路径都必须具有最小长度"使用这一量度标提供快速的最短路径查找&准!假定已经构造了!条最短路径!则下面要构造"=!利用结点入度信息查找的路径应该是下一条最短的最小长度路径"根据结点的入度信息来优化查找最短路径的如何根据贪心算法!确定路径上的每个节点基本思想是,当某结点的入度为$时!图中其他结而最终求得最短路径!’(