传统的最短路算法主要有Floyd算法[ 1 ]和Dijkstra算法[ 2 ]等. 其中Floyd算 法主要用于计算所有节点对之间的最短路;而Dijkstra 算法是一种用于计算从一个源节点到其所有宿节点最短路的高效算法.本文提出其优化的算法!

第28卷　第2期　2009年3月

文章编号:1671-9824(2009)02-0010-04

许昌学院学报

JOURNALOFXUCHANGUNIVERSITYVol.28.No.2

Mar.2009

最短路问题的Floyd算法优化

张德全,吴果林

(桂林航天工业高等专科学校,)

　　摘　要:,通过构造求解最短路径的迭代矩阵和序号矩阵优化了Fl,,并且路径寻找简单、直观、高效.

关键词:;;::A

0　引言

最短路作为图与网络技术研究中的一个经典问题一直在工程规划、地理信息系统、通信和军事运筹学等领域有着十分广泛的应用,对该问题求解算法的设计和改进有着重要的理论和应用价值.目前,关于最短路问题的研究已有较多结果.传统的最短路算法主要有Floyd算法

[1]

和Dijkstra算法

[2]

等.其中Floyd算

法主要用于计算所有节点对之间的最短路;而Dijkstra算法是一种用于计算从一个源节点到其所有宿节点最短路的高效算法.文献[1]提出的Floyd算法是通过权矩阵计算来实现的一种方法,其主要思想是从代表任意两个节点vi到vj距离的带权邻接矩阵D开始,首先计算D

(0)

(0)

(1)

,即计算vi到vj经过一次经转的

(1)

所有可能路径,经过比较后选出最短路,代替D中对应的路径,迭代列出距离矩阵D的最短路.在此基础上依次计算D

k

(2)

,D

(1)

中各元素表

示通过一次迭代后网络中任意两点间最短路,也即网络中任意两点之间直接到达或只经过一个中间点时

,D

(3)

,…,D

(k)

,D

(k)

中对应的元素表示任意两点间不经过中间点或最时,表明得到的带权邻接矩阵D就反映了所有

(k)

多允许经过2-1个中间点时的最短路.当D

第一步,作初始距离矩阵D

dij

(0)

(0)

()

(k+1)

=D

(k)

[3]

顶点对之间的最短距离信息,成为最短距离矩阵.其算法(记为算法1)如下:

=(dij),其中:

Wij,i,j相邻对

∞,i,j不相邻或无路时

()

,(i,j=1,2,…,n);

第二步,构造迭代矩阵D第三步,若D

(k+1)

(k)

k

=(dij),其中:

dij

(k)

=min{dir

(k-1)

+drj

(k-1)

r=1,2,…,n};

=D

(k)

,迭代终止.否则,返回第二步.

对Floyd算法进行分析,不难发现在不含负回路的网络中存在以下问题:

(1)在计算两点vi和vj之间最短路时,每次都要计算n次加法,且插入的中间节点vr很明显不能使路

长变短,降低了计算效率样再去查dil

(k-1)

[4]

;

(k)

(k)

(2)若要找出点vi、vj间的最短路,则要回头去查是如何计算出vij的,不妨设dij=dil

(k-1)

+dlj

(k-1)

,同

、dlj

(k-1)

是如何算出的,…,一直查到D中的元素为止,才能找出所求最短路.

(0)

显然上述寻找最短路径的方法不直观、比较繁琐.基于这两点不足,本文在不含负回路的网络中对Floyd算法进行了优化,不仅简化了计算量,而且使得在寻找最短路径时更简洁方便.

收稿日期:2008-10-07

基金项目:广西省自然科学基金项目(2008M1002)

作者简介:张德全(1959—),男,河南漯河人,副教授,研究方向:最优化理论.