第23卷第9期 2002年9月
文章编号:1000-1220(2002) 09-1083-05
小型微型计算机系统M IN I -M I CRO SY ST EM V ol. 23N o. 9 Sep . 2002
网络最短路问题的改进算法
王晓东 陈国龙 林柏钢
(福州大学计算机科学与技术系, 福建福州350002)
摘 要:本文着重研究著名的Dijkstr a 网络最短路算法的实现效率, 提出算法实现的若干技巧, 大大提高了Dijkstra 最
短路算法的适用性和时间空间效率.
关键词:网络; 最短路; Dijkst ra 算法; 算法效率. 中图分类号:T P 311 文献标识码:A
1 引 言
网络最短路问题是网络优化领域中最常见的基本问题之一. 许多网络优化问题都以最短路问题为其子问题. 因此, 在网络的实际应用中, 最短路算法的效率显得越来越重要, 受到国内外学者的普遍关注. 本文着重研究著名的Dijkstr a 最短路算法的实现效率, 提出算法实现的若干技巧, 大大提高了Dijkstra 最短路算法的适用性和时间空间效率.
一个网络N 是一个赋权有向图G=(V , E) , 其中每一条边(u , v ) ∈E 都有一边权c (u , v ) ∈R . 网络最短路问题所关心的是求网络中一给定顶点s ∈V (称为源) 到网络中所有其他顶点间的最短路. 这里所说的路的长度是指路上各边权的和. 迄今为止大多数的网络最短路算法可纳入下面的算法框架
〔4〕
络N 是一个非负网络, 即对任意(u, v ) ∈E 有c 〔u, v 〕≥0时,
如果我们让Selec t(U ) 从当前标号顶点集U 中选取当前路长D 最短的顶点u , 即D (u ) =min {D (v ) |v ∈U }, 我们就得到著名的Dijkstra 最短路算法.
本文中设|V |=n , |E |=m . 如果用堆来存储标号顶点集U , 则Dijkst ra 最短路算法所需的计算时间为O (m log n ) 〔1〕. 下面我们要讨论当边权为非负整数时, 对Dijkstra 最短路算法的时间和W 空间效率的改进.
2 桶算法设计
设网络N 各边的权值为0到C-1之间的整数, C 为一正整数.
注意到Dijkst ra 算法的关键在于从当前标号顶点集U 中选取当前路长D 最短的顶点u , 即D (u )=min {D (v ) |v ∈U }.而对任意u, v ∈U , 且D 〔u 〕
〔v 〕
〔w 〕+c (w , v ) ≤D 〔u 〕+C-1. 换句话说, 在任一时刻, U 中顶
点最多有C 个不同的D 值. 即在任一时刻, 总存在常数a , 使得对任意v ∈U 有a ≤D 〔v 〕≤a +C-1.
由此我们想到可以用桶排序算法的思想, 设置若干个桶来存放U 中的元素, 使得当v ∈U 时, 将顶点v 存放在D 〔v 〕号桶中. 显然, 在任何时刻对任意v ∈V , 从源s 到v 的当前最短路长D (v ) 有0≤D (v ) ≤(n -1) (C -1). 因此在最坏情况下需要O (nC ) 的桶空间. 由于在任一时刻, U 中顶点最多有C 个不同的D 值, 我们可以将所需的桶空间从O (nC) 减少到只需要C 个桶. 这里可能遇到的一个问题是, 在算法执行过程中, a 值可能不断增大. 为了解决这个问题, 我们可以设置一个游标k 指示出当前最小桶编号的位置. U 中元素最多存放在其后的C -1个桶中. 当顺序的C 个桶超出桶头数组的界时, 可用循环数组的思想再从头开始存放. 桶中顶点可用一个循环链表来存储. 由于在每个桶中存入一个顶点需要O (1) 时间. 算法Select 除了对链表的处理时间外, 还需要O (C) 计算时间. 因为在整个算法中E 的每条边处理一次, 故算法对链表
.
Begin
Proced ure Sh ortes tPath s(V, E, c, s );
D 〔s 〕:=0; U :={s};
≠s ) Do D 〔u 〕:=+∞; Fo r (u
W hile (U ≠Υ) Do Begin
u :=Select (U );
Delete (u , U ) ;
Fo r (u , v ) ∈E Do
If (D 〔u 〕+c 〔u, v 〕
D 〔v 〕:=D 〔u 〕+c 〔u, v 〕;
Ins ert(v, U);
End; End; End;
其中集合U 是标号顶点集. Select(U ) 从当前标号顶点集U 中选取一个顶点. Delete (u , U ) 将顶点u 从当前标号顶点集U 中删去. Inser t (v , U ) 将顶点v 插入当前标号顶点集U 中.
Selec t(U ) 的不同实现方式导致不同的最短路算法. 当网
收稿日期:2001-03-12 基金项目:国家(973G 1998030600T ) 项目资助; 福建省科技厅杰出人才基金项目(2000Z 148) 资助. 作者简介:王晓东, 教授, 研究领域为数据结构, 算法设计与分析.
1084
小 型 微 型 计 算 机 系 统 2002年
处理所需的总时间为O (m ). 由此可知上述Dijkstra 最短路桶算法需要O (m+Cn) 计算时间和O (m +n +C) 空间〔1, 2〕.
我们注意到, 当网络N 中各边权的最大值C 不太大时, 上述O (m+Cn) 计算时间的桶算法是对O (m log n ) 〔1〕时间Di-jkstr a 最短路算法的改进. 而当C 值较大时桶算法的效率明显降低. 更严重的是在实际计算时的空间需求得不到满足, 导致计算失败. 鉴于这种情况, 我们提出对上述最短路桶算法的2个改进算法, 进一步降低算法的时空需求.
3 算法的改进
3. 1 桶空间压缩算法
在最短路桶算法中, 每个桶中存储的顶点具有相同的最短路长. 在一般情况下, 每个桶中只有少量的顶点, 甚至有许多空桶. 为了节省桶空间, 提高算法效率, 我们将连续的桶空间均匀地划分为[C /L]段, 每段中的L 个桶合并为一个桶, 如图1所示
.
图1 桶空间压缩
在合并后的桶中, 所有桶中顶点按先进先出的原则组织成队列, 依据Sho rtest Paths 所给的算法框架进行计算. 下面我们根据上述思想来描述桶压缩算法的数据结构及其算法实现策略.
首先采用紧凑邻接表来表示给定的网络N , 即将通常表示网络的邻接表的顶点表数组中各顶点所相应的边表用一个边表数组紧凑地存储〔3〕. 其中顶点和边的数据类型node 和ar c 说明如下.
Type
nodeP =↑node; arcP=↑arc; node=
R ecord
firs t , dis t , index :Longin t;
parent , next , prev :nodeP; status :Integer; End; arc =
Reco rd
len , head :Longint; End;
〕Of nodeP ; buck et =Array 〔0. . M AXLENGT H BucketHeap =
Record
size , base, curr , low :Longint; firs t:buck et; End;
其中size 表示桶数组的大小; base 表示当前路长基数;
cur r 表示当前桶数组中最短路长所对应的桶号; low 表示当前桶数组中循环存储部分最小桶号; first 是当前桶数组.
采用所述数据结构的桶空间压缩算法可描述如下.
Procedure BucketSP ;
Begin
InitHeap ; {桶初始化}W hile (T ru e) Do
Begin
DeleteM in (nodefrom ); {从桶中取出当前最短距离顶点
nodefrom }
If (n od efrom =Nil ) Th en Exit ;
las t :=nod es 〔nod efrom ↑. index+1〕↑. firs t-1; dis tfrom:=n od efrom ↑. dis t; {检查从nodefrom 发出的每一条边}For j :=nodefrom ↑. firs t To las t Do
Begin
nodeto :=nod es 〔arcs 〔〕〕; {nod eto 为当前边j ↑. h ead
所指向的顶点}
dis tnew:=dis tfrom +(arcs 〔j 〕↑. len) ; If (distnew
Begin
BucketPos (dis tnew , pos new ); {计算出应存入的桶号
posnew }
ins :=true;
If ((nod eto ↑. s tatus =0) ) Th en {顶点nodeto 已在桶
中}
Begin
dis told :=nodeto ↑. dist;
);
表示网络N 紧凑邻接表的顶点表数组nodes 和边表数
组a rcs 说明为:
nodes :Array 〔0. . M AXN 〕Of n od eP ; :Ar ray 〔0. . M AXM 〕Of arcP ; arcs
在第i 个顶点记录中, first 表示顶点i 的第一条出边在边表数组a rcs 中的位置; dist 表示顶点i 的当前最短距离; index
表示顶点i 在顶点表数组nodes 中的位置; par ent 表示顶点i 在当前最短路中的父顶点的编号; nex t 和pr ev 分别是指向顶点i 在桶链表中的下一个顶点和前一个顶点的指针; status 是表示顶点i 是否属于集合U 的标志变量.
在第i 条边的记录中, le n 表示该边的边长; head 表示该边所指向的顶点编号.
:
9期
If (posold posn ew ) :=false ; Else ins
End;
王晓东等:网络最短路问题的改进算法
Then R emove (nodeto ,
BHeap . low :=pos ;
End ;
1085
pos old) {将顶点nodeto 从桶中删去}
If (ins)Th en Ins ert(nodeto, pos new ); {将顶点nodeto 存
入桶posnew }
nod eto ↑. dist :=distnew; nod eto ↑. parent :=nodefrom;
End; End ; End; End ;
算法Delete Min(u) 实现网络最短路算法框架中u :=Se-lect (U ) 和Dele te(u, U ) 这2个计算步骤, 并在计算中调整桶中数据分布.
Procedure DeleteMin (var node :nodeP ); Label rep; Begin rep :
{找最小非空桶}
W hile ((B Heap . cu rr
BHeap. curr :=B Heap. cu rr +1; If (BHeap. curr=B Heap. size) Th en Begin
If (BHeap. low
B Heap . curr :=B Heap . low ;
B Heap . low :=B Heap . size ; B Heap. base :=BHeap. bas e +B Heap. size *L; Goto rep;
End
Else node :=Nil; End
Else {curr 为最小非空桶号} Begin
node :=BHeap . first 〔B Heap . cu rr 〕; node ↑. statu s :=1;
If (nod e ↑. nex t=nod e) Th en{桶中仅有一个顶点}
BHeap. firs t 〔BHeap. curr 〕:=Nil Else Begin
node ↑. prev ↑. next :=node ↑. n ext;
node ↑. nex t ↑. p rev :=node ↑. p rev ;
〕:=node ↑. nex t ; B Heap . firs 〔t BHeap . curr
End ; End; End;
其中Bucket Pos(dista nce, po s) 根据当前顶点的最短路长distance 计算出其应存入的桶号pos, 算法描述如下.
Procedure BucketPos (distance :longint ; var pos :longint );
begin
pos :=dis tance-B Heap. base;
:=pos DIV L ; pos
if pos>=BHeap. size then pos :=pos-B Heap. size els e if pos
End;
算法Remov e (node , pos ) 将顶点node 从桶pos 中删去.
Procedure Remove (node :nodeP ; pos :longint );
Begin
If (node ↑. n ext =node ) Then BHeap . firs t 〔pos 〕:=Nil Els e
Begin
node ↑. p rev ↑. nex t :=node ↑. nex t;
node ↑. next ↑. prev:=node ↑. prev; If (BHeap. first 〔pos 〕=node) Then
BHeap. firs t 〔pos 〕:=node ↑. nex t ; End ; End;
算法Inser t (node, po s) 将顶点node 存入桶po s 中.
Procedure Insert (node :nodeP ; pos :longint ); var tem p :nod eP ; Begin
If (B Heap. first 〔pos 〕=Nil) Then Begin
BHeap. firs t 〔pos 〕:=node;
node ↑. next :=node; node ↑. p rev:=node;
End Els e Begin temp :=B Heap . firs t 〔pos 〕;
↑. prev ↑. nex t :=node ; temp
node ↑. p rev:=temp ↑. p rev; node ↑. next :=temp; temp ↑. prev:=node;
End;
node ↑. s tatus :=0;
If () 3. 2 桶空间截断算法
桶空间截断算法的基本思想是预先设置桶数组长度L. 在桶号为0～L -1所表示的距离范围内, 按照通常的办法来存储顶点. 而将当前最短路长超过0～L-1号桶所表示的距离范围的顶点存入L 号桶. 在算法中不断执行DeleteM in 运算, 一旦出现0～L-1号桶均为空桶时, 将L 号桶中顶点重新分布到0～L-1号桶中.
Procedure DeleteMin (var node :nodeP ); var bound, dis tn ew , posnew:longin t; h ead, tail, nex tnode :nodeP; Label rep; Begin rep :
{找最小非空桶}
W hile ((BHeap. cur r
〔B Heap. cu rr 〕=Nil) ) Do
=1;
1086
小 型 微 型 计 算 机 系 统
BHeap . firs t 〔BHeap . curr 〕:=Nil
Else Begin
2002年
If (BHeap . cu rr =BHeap . s ize ) Then {0～L -1号桶均为空桶} Begin
If (BHeap . firs t 〔BHeap . size 〕Nil ) Th en {L 号桶非空} Begin
nod e :=B Heap . firs t 〔B Heap . size 〕;
↑. prev ↑. nex :nod e t =Nil ; {断开为非循环双链表}
:=BIG ; BHeap . bas e
w hile (node NIl ) do {计算新路长基数}
Begin
If node ↑. dis t
node ↑. dis t ; node :=node ↑. n ext ;
End ;
bound :=B Heap. base +BHeap. size; {顶点分布上界}
:=0; BHeap . cur r
tail :=Nil ; h ead :=Nil;
nod e :=B Heap. firs t 〔B Heap. size 〕;
～L -while (node NIl ) do {L 号桶中顶点重新分布到0
1号桶中}
Begin
nex tnode :=node ↑. next ;
distnew:=node ↑. dis t ;
If (distnew
Begin
BucketPos (distnew, pos new );
Ins ert(node, posnew );
End
Else{保留在L 号桶中} Begin
If (tail Nil) Then Begin
tail ↑. next :=node;
nod e ↑. prev:=tail;
End
Else h ead :=node;
tail :=node;
End;
nod e :=nextnode; End;
If (tail Nil) Then{置为循环链表} Begin
tail ↑. next :=head;
h ead ↑. prev:=tail ;
End;
BHeap. firs t 〔BHeap. size 〕:=h ead;
Goto rep;
End
Els e node :=Nil; {U= } End
Els e{cu rr 为最小非空桶号} Begin
node :=B Heap. firs t 〔BHeap. curr 〕;
node ↑. s tatus :=1;
If . n node ↑. prev ↑. n ext :=node ↑. nex t;
node ↑. nex t ↑. p rev :=node ↑. prev; BHeap. firs t 〔BHeap. curr 〕:=node ↑. nex t;
End; End; End;
由于数据结构的改变, 桶中顶点不需要循环存储, 根据当
前顶点的最短路长dista nce 计算出其应存入的桶号pos 的算法Bucket Po s (distance , pos ) 作相应调整如下.
:longint ; var pos :longint ); Procedure BucketPos (distance
b egin
pos :=distance-BHeap. bas e;
if pos >B Heap. size th en pos :=BHeap. size els e if pos
由此可设计出网络最短路的桶空间截断算法.
4 算法复杂性分析
4. 1 桶空间压缩算法的计算复杂性
桶空间压缩算法需要[C /L]个桶, 桶中每个顶点需要O (1) 存储空间. 除了紧凑邻接表所需要的O (m +n ) 空间外, 尚需O (n +C /L) 的存储空间. 因此桶空间压缩算法所需的存储空间为O (m +n +C /L ).
由于在桶空间压缩算法中, 每个桶中顶点是按照队列组织存放的, 所以一个顶点可能多次进出同一桶顶点队列. 而当同一顶点重复进入桶顶点队列时, 其当前最短距离至少减1. 因此同一顶点进入同一桶顶点队列的次数不超过L 次. 每个顶点进出队列一次所需的处理时间为O (1) , 每一条边所需的处理时间也是O (1) , 由此可见, 对桶中所有顶点进行处理所需的时间是O (L(m+n) ). 另一方面, 算法DeleteM in 的搜索非空桶的W hile 循环体需要O (C /L ) 计算时间, 而循环体最多被执行n 次, 因此算法中搜索非空桶所需的总时间为O (nC /L ).
综上可知, 桶空间压缩算法所需的计算时间为O (m L+n (L +C /L ) ). 4. 2 桶空间截断算法的计算复杂性
桶空间截断算法所需的空间显然为O (L +n ). 在桶空间截断算法中, 第0～L-1号桶中顶点的组织方式与桶算法完全一致. 桶中每个顶点恰被处理一次. 因此对桶中所有顶点进行处理所需的总时间为O (m +n). 桶空间截断算法与桶算法的主要区别在于截断的第L 号桶中顶点的重新分布. 在每一次作顶点重新分布时, 插入到0～L-1号桶中顶点所需的处理时间可用簿记的方法来计算. 每个顶点插入到每个桶中至多一次, 总共有L 个桶, 故所需的计算时间为O (nL). 另外, 在每一次重新分布后保留在第L 号桶中的顶点所需的处理时间也可用簿记的方法来计算. 每一次重新分布L 号L , L 号
9期 王晓东等:网络最短路问题的改进算法
1087
多重新分布C /L 次. 每一次重新分布扫描一个顶点所需时间为O (1) , 因此保留在第L 号桶中顶点所需的处理时间为O (nC /L ).
综上可知, 桶空间截断算法所需的计算时间为O (m+n (L +C /L ) ).
在用桶空间压缩算法和桶空间截断算法且边权变化范围较大时取L =
U . 实际计算的结果如表2所示. 表2 大范围变边权实验结果
边权变化区间〔1. . 1〕〔0. . 10〕〔0. . 100〕〔0. . 10000〕〔0. . 1000000〕
桶算法1. 54. 129. 0323. 17内存溢出
桶空间压缩算法
2. 713. 884. 665. 806. 23
桶空间截断算法
1. 772. 072. 182. 233. 20
5 算法实验比较分析
对于网络最短路的桶算法和本文提出的桶空间压缩算法和桶空间截断算法从常规小边权和大范围变边权2个方面进行了实验比较, 所得的实验结果与理论分析完全一致. 5. 1 常规小边权实验结果对于边权在〔0…10〕范围内随机生成的非负网络用上述3个算法实际计算的结果如表1所示.
表1 常规小边权实验结果
结点数/边数桶算法桶空间压缩算法
512/655360. 090. 021024/262144
0. 46
0. 110. 481. 95
2048/10485761. 974096/41943048. 37
桶空间截断算法
0. 02
0. 120. 492. 02
表中所列计算时间为秒. 测试所用机型为P Ⅲ850, 128M 内存.
从上述实验结果可以看出, 当边权变化范围较大时, 桶空间压缩算法和桶空间截断算法均明显优于桶算法. 桶空间截断算法略优于桶空间压缩算法.
参 考 文 献
1Cormen T. H. , Leis ers on C. E. , R iv es t R. L. . Introduction to 〔M 〕. M IT Press , Camb ridg e , M A , 1990. 429～433algo rith ms
2Dial R . B. . Algo rith m 360:sho rtest path fores t w ith topological ordering 〔J 〕. Comm. ACM 12, 1969. 632～633
3Sahni S . . Data s tructures , algorithms , and applications in C ++〔M 〕. M cGraw Hill, New Yo rk , 1998. 569～570
4W ang Xiao -d ong . Th e d esing and analysis of comp uter algo rith ms 〔M 〕. Beijing :Publish ing House of Electronics Ind ustry. 2001(王晓东. 计算机算法设计与分析〔M 〕. 北京, 电子工业出版社. 2001. 94～96)
表中所列计算时间为秒. 测试所用机型为P Ⅲ850, 128M
内存.
从上述实验结果可以看出, 对于常规小边权, 桶空间压缩算法和桶空间截断算法均优于桶算法. 桶空间压缩算法和桶空间截断算法之间的差别不大.
5. 2 大范围变边权实验结果
对于130000个结点和500000条且边权在〔L . . U 〕范围内随机变化的非负网络对上述3个算法进行实际计算比较.
Improved Algorithms for Network Shortest Paths Problem
W AN G Xia o-do ng , CHEN Guo-lo ng , L IN Bo-ga ng
(Computer Science Depar tment of F uzhou University , Fuz hou 350002, Ch ina )
Abstract This paper discusses the desig n and im plementatio n strategies of the famo us Dijkstr a sho r test paths alg o rithm. The new techniques sugg ested improv e the time and space co mplexities o f the sho r test pa th s alg orithm sig nificantly . Key words netw o rks; sho rtest paths; dijkstr a alg o rithm; algo rithm efficie ncy
第23卷第9期 2002年9月
文章编号:1000-1220(2002) 09-1083-05
小型微型计算机系统M IN I -M I CRO SY ST EM V ol. 23N o. 9 Sep . 2002
网络最短路问题的改进算法
王晓东 陈国龙 林柏钢
(福州大学计算机科学与技术系, 福建福州350002)
摘 要:本文着重研究著名的Dijkstr a 网络最短路算法的实现效率, 提出算法实现的若干技巧, 大大提高了Dijkstra 最
短路算法的适用性和时间空间效率.
关键词:网络; 最短路; Dijkst ra 算法; 算法效率. 中图分类号:T P 311 文献标识码:A
1 引 言
网络最短路问题是网络优化领域中最常见的基本问题之一. 许多网络优化问题都以最短路问题为其子问题. 因此, 在网络的实际应用中, 最短路算法的效率显得越来越重要, 受到国内外学者的普遍关注. 本文着重研究著名的Dijkstr a 最短路算法的实现效率, 提出算法实现的若干技巧, 大大提高了Dijkstra 最短路算法的适用性和时间空间效率.
一个网络N 是一个赋权有向图G=(V , E) , 其中每一条边(u , v ) ∈E 都有一边权c (u , v ) ∈R . 网络最短路问题所关心的是求网络中一给定顶点s ∈V (称为源) 到网络中所有其他顶点间的最短路. 这里所说的路的长度是指路上各边权的和. 迄今为止大多数的网络最短路算法可纳入下面的算法框架
〔4〕
络N 是一个非负网络, 即对任意(u, v ) ∈E 有c 〔u, v 〕≥0时,
如果我们让Selec t(U ) 从当前标号顶点集U 中选取当前路长D 最短的顶点u , 即D (u ) =min {D (v ) |v ∈U }, 我们就得到著名的Dijkstra 最短路算法.
本文中设|V |=n , |E |=m . 如果用堆来存储标号顶点集U , 则Dijkst ra 最短路算法所需的计算时间为O (m log n ) 〔1〕. 下面我们要讨论当边权为非负整数时, 对Dijkstra 最短路算法的时间和W 空间效率的改进.
2 桶算法设计
设网络N 各边的权值为0到C-1之间的整数, C 为一正整数.
注意到Dijkst ra 算法的关键在于从当前标号顶点集U 中选取当前路长D 最短的顶点u , 即D (u )=min {D (v ) |v ∈U }.而对任意u, v ∈U , 且D 〔u 〕
〔v 〕
〔w 〕+c (w , v ) ≤D 〔u 〕+C-1. 换句话说, 在任一时刻, U 中顶
点最多有C 个不同的D 值. 即在任一时刻, 总存在常数a , 使得对任意v ∈U 有a ≤D 〔v 〕≤a +C-1.
由此我们想到可以用桶排序算法的思想, 设置若干个桶来存放U 中的元素, 使得当v ∈U 时, 将顶点v 存放在D 〔v 〕号桶中. 显然, 在任何时刻对任意v ∈V , 从源s 到v 的当前最短路长D (v ) 有0≤D (v ) ≤(n -1) (C -1). 因此在最坏情况下需要O (nC ) 的桶空间. 由于在任一时刻, U 中顶点最多有C 个不同的D 值, 我们可以将所需的桶空间从O (nC) 减少到只需要C 个桶. 这里可能遇到的一个问题是, 在算法执行过程中, a 值可能不断增大. 为了解决这个问题, 我们可以设置一个游标k 指示出当前最小桶编号的位置. U 中元素最多存放在其后的C -1个桶中. 当顺序的C 个桶超出桶头数组的界时, 可用循环数组的思想再从头开始存放. 桶中顶点可用一个循环链表来存储. 由于在每个桶中存入一个顶点需要O (1) 时间. 算法Select 除了对链表的处理时间外, 还需要O (C) 计算时间. 因为在整个算法中E 的每条边处理一次, 故算法对链表
.
Begin
Proced ure Sh ortes tPath s(V, E, c, s );
D 〔s 〕:=0; U :={s};
≠s ) Do D 〔u 〕:=+∞; Fo r (u
W hile (U ≠Υ) Do Begin
u :=Select (U );
Delete (u , U ) ;
Fo r (u , v ) ∈E Do
If (D 〔u 〕+c 〔u, v 〕
D 〔v 〕:=D 〔u 〕+c 〔u, v 〕;
Ins ert(v, U);
End; End; End;
其中集合U 是标号顶点集. Select(U ) 从当前标号顶点集U 中选取一个顶点. Delete (u , U ) 将顶点u 从当前标号顶点集U 中删去. Inser t (v , U ) 将顶点v 插入当前标号顶点集U 中.
Selec t(U ) 的不同实现方式导致不同的最短路算法. 当网
收稿日期:2001-03-12 基金项目:国家(973G 1998030600T ) 项目资助; 福建省科技厅杰出人才基金项目(2000Z 148) 资助. 作者简介:王晓东, 教授, 研究领域为数据结构, 算法设计与分析.
1084
小 型 微 型 计 算 机 系 统 2002年
处理所需的总时间为O (m ). 由此可知上述Dijkstra 最短路桶算法需要O (m+Cn) 计算时间和O (m +n +C) 空间〔1, 2〕.
我们注意到, 当网络N 中各边权的最大值C 不太大时, 上述O (m+Cn) 计算时间的桶算法是对O (m log n ) 〔1〕时间Di-jkstr a 最短路算法的改进. 而当C 值较大时桶算法的效率明显降低. 更严重的是在实际计算时的空间需求得不到满足, 导致计算失败. 鉴于这种情况, 我们提出对上述最短路桶算法的2个改进算法, 进一步降低算法的时空需求.
3 算法的改进
3. 1 桶空间压缩算法
在最短路桶算法中, 每个桶中存储的顶点具有相同的最短路长. 在一般情况下, 每个桶中只有少量的顶点, 甚至有许多空桶. 为了节省桶空间, 提高算法效率, 我们将连续的桶空间均匀地划分为[C /L]段, 每段中的L 个桶合并为一个桶, 如图1所示
.
图1 桶空间压缩
在合并后的桶中, 所有桶中顶点按先进先出的原则组织成队列, 依据Sho rtest Paths 所给的算法框架进行计算. 下面我们根据上述思想来描述桶压缩算法的数据结构及其算法实现策略.
首先采用紧凑邻接表来表示给定的网络N , 即将通常表示网络的邻接表的顶点表数组中各顶点所相应的边表用一个边表数组紧凑地存储〔3〕. 其中顶点和边的数据类型node 和ar c 说明如下.
Type
nodeP =↑node; arcP=↑arc; node=
R ecord
firs t , dis t , index :Longin t;
parent , next , prev :nodeP; status :Integer; End; arc =
Reco rd
len , head :Longint; End;
〕Of nodeP ; buck et =Array 〔0. . M AXLENGT H BucketHeap =
Record
size , base, curr , low :Longint; firs t:buck et; End;
其中size 表示桶数组的大小; base 表示当前路长基数;
cur r 表示当前桶数组中最短路长所对应的桶号; low 表示当前桶数组中循环存储部分最小桶号; first 是当前桶数组.
采用所述数据结构的桶空间压缩算法可描述如下.
Procedure BucketSP ;
Begin
InitHeap ; {桶初始化}W hile (T ru e) Do
Begin
DeleteM in (nodefrom ); {从桶中取出当前最短距离顶点
nodefrom }
If (n od efrom =Nil ) Th en Exit ;
las t :=nod es 〔nod efrom ↑. index+1〕↑. firs t-1; dis tfrom:=n od efrom ↑. dis t; {检查从nodefrom 发出的每一条边}For j :=nodefrom ↑. firs t To las t Do
Begin
nodeto :=nod es 〔arcs 〔〕〕; {nod eto 为当前边j ↑. h ead
所指向的顶点}
dis tnew:=dis tfrom +(arcs 〔j 〕↑. len) ; If (distnew
Begin
BucketPos (dis tnew , pos new ); {计算出应存入的桶号
posnew }
ins :=true;
If ((nod eto ↑. s tatus =0) ) Th en {顶点nodeto 已在桶
中}
Begin
dis told :=nodeto ↑. dist;
);
表示网络N 紧凑邻接表的顶点表数组nodes 和边表数
组a rcs 说明为:
nodes :Array 〔0. . M AXN 〕Of n od eP ; :Ar ray 〔0. . M AXM 〕Of arcP ; arcs
在第i 个顶点记录中, first 表示顶点i 的第一条出边在边表数组a rcs 中的位置; dist 表示顶点i 的当前最短距离; index
表示顶点i 在顶点表数组nodes 中的位置; par ent 表示顶点i 在当前最短路中的父顶点的编号; nex t 和pr ev 分别是指向顶点i 在桶链表中的下一个顶点和前一个顶点的指针; status 是表示顶点i 是否属于集合U 的标志变量.
在第i 条边的记录中, le n 表示该边的边长; head 表示该边所指向的顶点编号.
:
9期
If (posold posn ew ) :=false ; Else ins
End;
王晓东等:网络最短路问题的改进算法
Then R emove (nodeto ,
BHeap . low :=pos ;
End ;
1085
pos old) {将顶点nodeto 从桶中删去}
If (ins)Th en Ins ert(nodeto, pos new ); {将顶点nodeto 存
入桶posnew }
nod eto ↑. dist :=distnew; nod eto ↑. parent :=nodefrom;
End; End ; End; End ;
算法Delete Min(u) 实现网络最短路算法框架中u :=Se-lect (U ) 和Dele te(u, U ) 这2个计算步骤, 并在计算中调整桶中数据分布.
Procedure DeleteMin (var node :nodeP ); Label rep; Begin rep :
{找最小非空桶}
W hile ((B Heap . cu rr
BHeap. curr :=B Heap. cu rr +1; If (BHeap. curr=B Heap. size) Th en Begin
If (BHeap. low
B Heap . curr :=B Heap . low ;
B Heap . low :=B Heap . size ; B Heap. base :=BHeap. bas e +B Heap. size *L; Goto rep;
End
Else node :=Nil; End
Else {curr 为最小非空桶号} Begin
node :=BHeap . first 〔B Heap . cu rr 〕; node ↑. statu s :=1;
If (nod e ↑. nex t=nod e) Th en{桶中仅有一个顶点}
BHeap. firs t 〔BHeap. curr 〕:=Nil Else Begin
node ↑. prev ↑. next :=node ↑. n ext;
node ↑. nex t ↑. p rev :=node ↑. p rev ;
〕:=node ↑. nex t ; B Heap . firs 〔t BHeap . curr
End ; End; End;
其中Bucket Pos(dista nce, po s) 根据当前顶点的最短路长distance 计算出其应存入的桶号pos, 算法描述如下.
Procedure BucketPos (distance :longint ; var pos :longint );
begin
pos :=dis tance-B Heap. base;
:=pos DIV L ; pos
if pos>=BHeap. size then pos :=pos-B Heap. size els e if pos
End;
算法Remov e (node , pos ) 将顶点node 从桶pos 中删去.
Procedure Remove (node :nodeP ; pos :longint );
Begin
If (node ↑. n ext =node ) Then BHeap . firs t 〔pos 〕:=Nil Els e
Begin
node ↑. p rev ↑. nex t :=node ↑. nex t;
node ↑. next ↑. prev:=node ↑. prev; If (BHeap. first 〔pos 〕=node) Then
BHeap. firs t 〔pos 〕:=node ↑. nex t ; End ; End;
算法Inser t (node, po s) 将顶点node 存入桶po s 中.
Procedure Insert (node :nodeP ; pos :longint ); var tem p :nod eP ; Begin
If (B Heap. first 〔pos 〕=Nil) Then Begin
BHeap. firs t 〔pos 〕:=node;
node ↑. next :=node; node ↑. p rev:=node;
End Els e Begin temp :=B Heap . firs t 〔pos 〕;
↑. prev ↑. nex t :=node ; temp
node ↑. p rev:=temp ↑. p rev; node ↑. next :=temp; temp ↑. prev:=node;
End;
node ↑. s tatus :=0;
If () 3. 2 桶空间截断算法
桶空间截断算法的基本思想是预先设置桶数组长度L. 在桶号为0～L -1所表示的距离范围内, 按照通常的办法来存储顶点. 而将当前最短路长超过0～L-1号桶所表示的距离范围的顶点存入L 号桶. 在算法中不断执行DeleteM in 运算, 一旦出现0～L-1号桶均为空桶时, 将L 号桶中顶点重新分布到0～L-1号桶中.
Procedure DeleteMin (var node :nodeP ); var bound, dis tn ew , posnew:longin t; h ead, tail, nex tnode :nodeP; Label rep; Begin rep :
{找最小非空桶}
W hile ((BHeap. cur r
〔B Heap. cu rr 〕=Nil) ) Do
=1;
1086
小 型 微 型 计 算 机 系 统
BHeap . firs t 〔BHeap . curr 〕:=Nil
Else Begin
2002年
If (BHeap . cu rr =BHeap . s ize ) Then {0～L -1号桶均为空桶} Begin
If (BHeap . firs t 〔BHeap . size 〕Nil ) Th en {L 号桶非空} Begin
nod e :=B Heap . firs t 〔B Heap . size 〕;
↑. prev ↑. nex :nod e t =Nil ; {断开为非循环双链表}
:=BIG ; BHeap . bas e
w hile (node NIl ) do {计算新路长基数}
Begin
If node ↑. dis t
node ↑. dis t ; node :=node ↑. n ext ;
End ;
bound :=B Heap. base +BHeap. size; {顶点分布上界}
:=0; BHeap . cur r
tail :=Nil ; h ead :=Nil;
nod e :=B Heap. firs t 〔B Heap. size 〕;
～L -while (node NIl ) do {L 号桶中顶点重新分布到0
1号桶中}
Begin
nex tnode :=node ↑. next ;
distnew:=node ↑. dis t ;
If (distnew
Begin
BucketPos (distnew, pos new );
Ins ert(node, posnew );
End
Else{保留在L 号桶中} Begin
If (tail Nil) Then Begin
tail ↑. next :=node;
nod e ↑. prev:=tail;
End
Else h ead :=node;
tail :=node;
End;
nod e :=nextnode; End;
If (tail Nil) Then{置为循环链表} Begin
tail ↑. next :=head;
h ead ↑. prev:=tail ;
End;
BHeap. firs t 〔BHeap. size 〕:=h ead;
Goto rep;
End
Els e node :=Nil; {U= } End
Els e{cu rr 为最小非空桶号} Begin
node :=B Heap. firs t 〔BHeap. curr 〕;
node ↑. s tatus :=1;
If . n node ↑. prev ↑. n ext :=node ↑. nex t;
node ↑. nex t ↑. p rev :=node ↑. prev; BHeap. firs t 〔BHeap. curr 〕:=node ↑. nex t;
End; End; End;
由于数据结构的改变, 桶中顶点不需要循环存储, 根据当
前顶点的最短路长dista nce 计算出其应存入的桶号pos 的算法Bucket Po s (distance , pos ) 作相应调整如下.
:longint ; var pos :longint ); Procedure BucketPos (distance
b egin
pos :=distance-BHeap. bas e;
if pos >B Heap. size th en pos :=BHeap. size els e if pos
由此可设计出网络最短路的桶空间截断算法.
4 算法复杂性分析
4. 1 桶空间压缩算法的计算复杂性
桶空间压缩算法需要[C /L]个桶, 桶中每个顶点需要O (1) 存储空间. 除了紧凑邻接表所需要的O (m +n ) 空间外, 尚需O (n +C /L) 的存储空间. 因此桶空间压缩算法所需的存储空间为O (m +n +C /L ).
由于在桶空间压缩算法中, 每个桶中顶点是按照队列组织存放的, 所以一个顶点可能多次进出同一桶顶点队列. 而当同一顶点重复进入桶顶点队列时, 其当前最短距离至少减1. 因此同一顶点进入同一桶顶点队列的次数不超过L 次. 每个顶点进出队列一次所需的处理时间为O (1) , 每一条边所需的处理时间也是O (1) , 由此可见, 对桶中所有顶点进行处理所需的时间是O (L(m+n) ). 另一方面, 算法DeleteM in 的搜索非空桶的W hile 循环体需要O (C /L ) 计算时间, 而循环体最多被执行n 次, 因此算法中搜索非空桶所需的总时间为O (nC /L ).
综上可知, 桶空间压缩算法所需的计算时间为O (m L+n (L +C /L ) ). 4. 2 桶空间截断算法的计算复杂性
桶空间截断算法所需的空间显然为O (L +n ). 在桶空间截断算法中, 第0～L-1号桶中顶点的组织方式与桶算法完全一致. 桶中每个顶点恰被处理一次. 因此对桶中所有顶点进行处理所需的总时间为O (m +n). 桶空间截断算法与桶算法的主要区别在于截断的第L 号桶中顶点的重新分布. 在每一次作顶点重新分布时, 插入到0～L-1号桶中顶点所需的处理时间可用簿记的方法来计算. 每个顶点插入到每个桶中至多一次, 总共有L 个桶, 故所需的计算时间为O (nL). 另外, 在每一次重新分布后保留在第L 号桶中的顶点所需的处理时间也可用簿记的方法来计算. 每一次重新分布L 号L , L 号
9期 王晓东等:网络最短路问题的改进算法
1087
多重新分布C /L 次. 每一次重新分布扫描一个顶点所需时间为O (1) , 因此保留在第L 号桶中顶点所需的处理时间为O (nC /L ).
综上可知, 桶空间截断算法所需的计算时间为O (m+n (L +C /L ) ).
在用桶空间压缩算法和桶空间截断算法且边权变化范围较大时取L =
U . 实际计算的结果如表2所示. 表2 大范围变边权实验结果
边权变化区间〔1. . 1〕〔0. . 10〕〔0. . 100〕〔0. . 10000〕〔0. . 1000000〕
桶算法1. 54. 129. 0323. 17内存溢出
桶空间压缩算法
2. 713. 884. 665. 806. 23
桶空间截断算法
1. 772. 072. 182. 233. 20
5 算法实验比较分析
对于网络最短路的桶算法和本文提出的桶空间压缩算法和桶空间截断算法从常规小边权和大范围变边权2个方面进行了实验比较, 所得的实验结果与理论分析完全一致. 5. 1 常规小边权实验结果对于边权在〔0…10〕范围内随机生成的非负网络用上述3个算法实际计算的结果如表1所示.
表1 常规小边权实验结果
结点数/边数桶算法桶空间压缩算法
512/655360. 090. 021024/262144
0. 46
0. 110. 481. 95
2048/10485761. 974096/41943048. 37
桶空间截断算法
0. 02
0. 120. 492. 02
表中所列计算时间为秒. 测试所用机型为P Ⅲ850, 128M 内存.
从上述实验结果可以看出, 当边权变化范围较大时, 桶空间压缩算法和桶空间截断算法均明显优于桶算法. 桶空间截断算法略优于桶空间压缩算法.
参 考 文 献
1Cormen T. H. , Leis ers on C. E. , R iv es t R. L. . Introduction to 〔M 〕. M IT Press , Camb ridg e , M A , 1990. 429～433algo rith ms
2Dial R . B. . Algo rith m 360:sho rtest path fores t w ith topological ordering 〔J 〕. Comm. ACM 12, 1969. 632～633
3Sahni S . . Data s tructures , algorithms , and applications in C ++〔M 〕. M cGraw Hill, New Yo rk , 1998. 569～570
4W ang Xiao -d ong . Th e d esing and analysis of comp uter algo rith ms 〔M 〕. Beijing :Publish ing House of Electronics Ind ustry. 2001(王晓东. 计算机算法设计与分析〔M 〕. 北京, 电子工业出版社. 2001. 94～96)
表中所列计算时间为秒. 测试所用机型为P Ⅲ850, 128M
内存.
从上述实验结果可以看出, 对于常规小边权, 桶空间压缩算法和桶空间截断算法均优于桶算法. 桶空间压缩算法和桶空间截断算法之间的差别不大.
5. 2 大范围变边权实验结果
对于130000个结点和500000条且边权在〔L . . U 〕范围内随机变化的非负网络对上述3个算法进行实际计算比较.
Improved Algorithms for Network Shortest Paths Problem
W AN G Xia o-do ng , CHEN Guo-lo ng , L IN Bo-ga ng
(Computer Science Depar tment of F uzhou University , Fuz hou 350002, Ch ina )
Abstract This paper discusses the desig n and im plementatio n strategies of the famo us Dijkstr a sho r test paths alg o rithm. The new techniques sugg ested improv e the time and space co mplexities o f the sho r test pa th s alg orithm sig nificantly . Key words netw o rks; sho rtest paths; dijkstr a alg o rithm; algo rithm efficie ncy