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

第!$卷第"期湖北汽车工业学院学报)*+,!$-*,"
"009年/月Q;E-A.<;?REN=(5E,;B;,(H=@ADE+,-(=+@A+,(,E,=QEA,"009

基于!"#$%&’(的最短路径改进算法

罗理!王锋
!昆明理工大学信息工程与自动化学院#云南昆明/&00&$"

摘要!针对如何利用’()*+,-.算法来高效地查找图中任意两结点之间的最短路径这一问题#提出了"种优化方
法%其一是应用图中各结点的出入度来简化查找任意两结点之间的最短路径’其二是利用已求出的两点之间的最
短路径来快速获得其他结点之间的最短路径$
关键词!最短路径’最短路径算法’’()*+,-.算法’出入度
中图分类号!1230$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=<I?(AD,L=+L;-,=+,M.,LN=,O==A.-N(,-.-I,O;
A;D=+(A>-.MLNI,L=.<>;-(,LB;?’()*+,-.#,L=,O;;M,(B(P=DB=,L;D+O=-=N-;E>L,?;-O.-D#OL(KL
O=-=.MM<I(A>;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<I,L=+L;-,=+,M.,L.B;A>,L=;,L=-A;D=+4
?1@A%$(2%+L;-,=+,M.,L’.<>;-(,LB;?,L=+L;-,=+,M.,L’.<>;-(,LB;?’()*+,-.’;E,!(AD=>-==

随着社会的不断进步#最短路径算法在人们的是从固定的一个点到其他各点的最短路径问题$但
日常生活显得越来越重要$比如%每天开车去上班#是在实际生活中往往要求解决的不只是固定一点
应该选择哪条公路才能使自己到公司的费用最低&到其他点的最短路径#而是要求计算出任意两点之
时间最少#这是最短路径的问题’在网络路由中#怎间的最短距离$针对这个问题#本文主要讨论了怎
样选择最优的路由路径#这也是最短路径问题’在样利用’()*+,-.算法优化实现图中任意两点之间
交通旅游&城市规划以及电网架设中怎样使其耗费的最短路径问题$
的资金最少#这还是最短路径问题$由此可见对最
短路径问题的研究是非常有意义的$$基本思路
最短路径这一重要问题早在"#世纪初就已经
得到人们的高度重视#当时也有许多科学家研究这为了解决最短路径问题#首先应根据要求选取
一重要问题的求解方法$但直到$%&%年荷兰计算一种量度标准$然后将!个输入排成这种量度标准
机科学家’()*+,-.!迪杰斯特拉"才给出这一问题求要求的顺序#按照这种顺序一次输入一个量$如果
解的基本思想#并给出了算法$后来这个算法就成这个输入和当前已经构成的在这种量度意义的部
了众所周知的’()*+,-.算法#也成为了一代经典$分最优解加在一起能产生一个可行解#则把此输入
当时的’()*+,-.提出的这一算法主要解决的问题加到这部分最优解中#否则不加入$这种能够在某

收稿日期!!""#!"$!%&
作者简介!罗理!%’(!!"#男#湖南长沙人#硕士生#主要从事网络信息安全研究$
第!!卷第"期罗理等,基于’()*+,-.的最短路径改进算法!!!"

种量度意义下得到最优解的分级处理方法称为贪!(根据’()*+,-.算法思想!可以由图中结点的
心算法"出入度信息来提高各点之间最短路径的查找速度&
按照上面的思路!可以逐步地构造出这些最短"(在带权图中利用’()*+,-.算法找出部分结点
路径"使用迄今已经生成的所有路径长度之和作之间的最短路径后!若其他还没有找出最短路径的
为一种量度!为了使这一量度达到最小!单独的每结点可以利用前面已找出的最短路径信息为自己
一条路径都必须具有最小长度"使用这一量度标提供快速的最短路径查找&
准!假定已经构造了!条最短路径!则下面要构造"=!利用结点入度信息查找
的路径应该是下一条最短的最小长度路径"根据结点的入度信息来优化查找最短路