! 西北大学学报(自然科学版)
"##$ 年!# 月,第%$ 卷第 & 期,
/,0123- ,4 .,1)5678) 92:;718:)<(.3)013- =(:72(7 >?:):,2)
@ @ 收稿日期:"##%A#&A#B
@ @ 基金项目:陕西省教育厅自然科学专项基金资助项目(CD#!%#")
@ @ 作者简介:张@ 蕾(!EF$A),女,西北大学副教授,博士,从事知识抽取、算法设计、自然语言理解等方面的研究.
矩阵方法求赋权图中最短路的算法
张@ 蕾
(西北大学 计算机科学系,陕西 西安@ G!##FE)
摘要:目的@ 给出一些计算赋权图中任意两个节点之间最短路的算法.方法@ 利用矩阵方法.结果@ 给出了赋权图中任意两点之间最短路的算法;任意两点之间在含有最少边数情况下的最短路
算法;赋权图中的所有最短路算法,以及前 ! 条最短路的算法.结论@ 所研究的算法解决了传统
算法的某些不足,因基于矩阵运算,程序设计简单,实用性强.
关@ 键@ 词:矩阵;赋权图;最短路
中图分类号:HI%#!* F@ @ 文献标识码:J@ @ 文章编号:!###A"G$A#&"GA#$
@ @ 随着计算机的普及以及地理信息科学的发展,地
理信息系统(KL=)因其强大的功能得到日益广泛和深
入的应用[! M%]
.网络分析作为 KL= 最主要的功能之
一,在电子导航、交通旅游、城市规划以及电力、通讯等
各种管网、管线的布局设计中发挥了重要的作用,而网
络分析中最基本最关键的问题是最短路径问题[$]
.
D:NO8)13 算法和 P-, 最短路问题的好算法[& M G]
.但是,这两个算法都存
在一些不足:" D:NO8)13 算法用于求解一给定点到
其他所有点之间的最短路,但在最短路不惟一的情
况下,它不能求出这一点到其他所有点之间的全部
最短路;# P-, 间的最短路,但不能求出这一点到其他所有点之间
的全部最短路.
在实际问题中,我们感兴趣的不仅是赋权图中
某两点之间的最短路,除了提供这两点之间的最短
路之外,还希望提供这两点之间的一些其他距离相
对较短的路,即给出一些某两点的路的序列,而路长
是单调递增的;或者求出赋权图中两点之间的所有
路及对应的路长.然而,这一问题在传统算法中尚
未考虑,本文将利用矩阵方法,解决这一问题.
!" 算法基础
定义!@ 给定 " 阶矩阵 定
义矩阵间的乘运算"<"为Q:2{
其中 !%& # Q:2{
定义 #@ 简单图 , #(-,.)的权矩阵为 / #
(0%其中
0%& #

0%& ,@ @ 当(1% ,1& )# .,
R ,@ @
{ 否则
0%& 表示边(1% ,1& )# . 上的权重.
定理 !@ 设有方阵/(2)
#(02
%& )和/(3)
#
(03
%& ),其中 02
%& 和03
%& 分别表示从节点 % 到节点 & 间至
多包含 2 * ! 条边和 3 * ! 条边时最短路的长度,则/(4)
#(04
%& )# /(2)
< /(3)
, (!)
04
%& # Q:2{02
%& ,03
%& ,!
4

!
4
%& # Q:2{02
%) * 03
02
%) 03

则元素 04
%& 表示从节点 % 到节点 & 间至多包含 2 * 3 *
" 条边时最短路的长度.
证明@设!4%& # 02
%5 * 03
5& ,且02
%5 包含 " $ 2 *
! 条边,03
5& 包含 # $ 3 * ! 条边,则!4%& 就表示从节点
% 到节点 & 间通过中间节点 5 且包含 " * # $ 2 * 3 *
" 条边时的最短距离,因此 04
%& 表示从节点 % 到节点 &
间至多包含 2 * 3 * " 条边时的最短距离.
推论 !@ 令$423 # Q:2{!
4
则$423
为图 , 中从 2 到3的最短路的距离,且至多包含 2 * 3
* " 条边.
万方数据
推论 !! !"#"
的元素表示图 $ 中对应两个节点
(行节点与列节点)之间至多包含 " # # 条边时的最
短路的距离.
定义 "! 称!(%)
&('%
() )为简单图 $ &(*,+)
的距离矩阵.
为了在求出最短距离的同时,也求出最短路径,
需要引入路径矩阵来存储任意两点之间所求距离对
应的路径.
定义#! 对应于简单图 $ &(*,+)的距离矩阵
!(%)
$('%
() )的路径矩阵为 "(%)
$(,%
() ),其中
-%
() &
'%
(),对应从 ( 至)路径,当% . '%
() . &;
!,! 否则
{ .
!$ 赋权图中任意两点间的最短路
!/ %$ 算法 %
根据定理 #,有如下算法:
#)赋初值
!(%)
&('%

0
0
+'('%
() 1 % ,-. '%
() . & )
*/0- ,%
() & ()
0120 ,%
() & "
2 = %.
")循环计算
3/+10 2 $[1(4"##
" ].(
0
0
! '() 3 = # *( 0
#
"2
() & 5+-{'22##
(3 4 '22##
3) }$
& '"2##
(5 4 '"2##
5)
+' 5+-{#
" 2
() ,'"2##
() }& #
"2
()
*/0- ,"2
() = ,"2##
(5 4 ,"2##
5)
! ! ! '"2
() = #
"2
()
2 = 2 4 #
0-..
!/ !$ 算法复杂性
由于内循环包括从# 至0的6 个循环,而外循环
需要从 # 至1(4"##
" 次,因此,整个算法复杂性为
6("6
1(4").
注:如果在循环计算中增加存储 %
%
%2 的存储单
元,则每步都可得到图 $ 中某两点之间的最短路长
及对应的路径.以下算法类似.
"$ 赋权图中两点之间含有最少边路
实际问题中,有时还要求计算任意两点之间含
有最少边数的最短路.例如,如果所求网络为实际
789 问题的网络,则节点就表示交叉路口.求最短路
的目的之一是用最少时间走完这段路,而交叉路口
多会影响行驶的时间.因此,计算任意两点之间含有
最少边数情况下的最短路是有实际意义的.
简单修改以上算法,这样的问题很容易完成.
算法 !$ (求赋权图中节点 ( 与)之间含有最少
边数的路的算法)
#)赋初值
!(%)
&('%

0
0
+'('%
() 1 % ,-. '%
() . & )
*/0- ,%
() & ()
0120 ,%
() & "
2 = %.
")循环计算
3/+10('2
2

0
0
! '() 3 = # *( 0
! #
24#
() & 5+-{'2
(3 4 '%
3) }!
& '2
(5 4 '%
5)
! +' 5+- {#
24#
() ,'2
() }& #
24#
()
! */0- ,24#
() = ,2
(5 4 ,%
5)
24#
() = #
24#
()
2 = 2 4 #
0-..
此时,'2
() 就是节点 ( 与)之间含有最少边数(边
数为 2)的路,,2
() 就是对应的路径.
注:如果既要求距离尽可能短,又要求边数一
定,可结合算法 # 和算法 " 计算.
#$ 赋权图中所有最短路
如果赋权图中的最短路不惟一时,上面的算法
只求出了其中的一条最短路.为了求出赋权图中的
所有最短路,需要修改上面的算法.实际上,在计算
'7
() 时,只要记录下对应于最小值的所有路径即可.
定义 &! 对应于简单图 $(*,+)的距离矩阵
!(%)
$('%
() )的所有路径矩阵为 #"(%)
$(8,%
() ),其中
—:";— 西北大学学报(自然科学版)第6< 卷
万方数据
!"#
$% !
&#
$% ,对应于 $ 至%所有路径,当"#&#
$% # $
!,% 否则{ .
即!"#
$% 表示是一个字符串集合.
简单修改算法 &,即可求出赋权图中任意两节
点之间的所有最短路及对应的路长.
!" 赋权图中前 ! 条最短路
实际问题中,希望在得到最短路的同时,还希望
得到次优、再次优,乃至前 ' 条最短路及对应的路径.
定义 !% 给定 ' 阶矩阵 矩
阵间的乘运算" 5"定义如下:
" 5

其中,是对{从小到
大的排序.
算法 #" (求赋权图中前 - 条最短路及对应路
径的算法)
&)赋初值
.(")
!(&"



/.(&"
$% 0 " 123 &"
$% # $ )
+452 ""
$% ! $%
56(5 ""
$% ! "
/=".
7)循环计算
84/65 /$[6)9' : &
7 ]3)



% &7/
7/ : &
$% ,&7/ : &
$* , &7/ : &
*% }
/=/ , &
523.
注:&7/
表示在包含至多 7/
条边时节点 $ 与%之间所有路长的一个非增排序.因此,在求赋权图中
前-条最短路时,只要在 &7/
$% 数组中取前 - 个即可.
如果对 - 不加限制,就可以得到赋权图中所有的路
(按非增序列排序).
$" 算" 例图&是一个实际的铁路;公路网络运输图,要将
物资分别从 <& ,<7 ,…,<= 运送到 >& ,>7 ,…,>&? .图
中粗线表示铁路,单细线和双细线表示公路,圆圈表
示火车站,每段铁路、公路旁的数字表示里程(@A).
每单位物资的铁路运价如图 7 所示.
图&% 铁路;公路网络运输图
B/9C &% D1/681E;4/9481E +*12(F)*+1+/)2 25+8)*@
—G7?—第?期%张% 蕾:矩阵方法求赋权图中最短路的算法
万方数据
图!" 每单位物资的铁路运价
0,/*+/ 12 .()$*
每单位物资的公路运价为:3& 4 万元5 67.
!" 结" 论
给出了一类用矩阵方法求解赋权图中任意两点
之间最短路的算法.不但可以求出赋权图中任意两
点之间的最短路、任意两点之间的所有最短路、两点
之间含有最少边数时的最短路,以及两点之间的前 !
条最短路.算法每循环一次,都能至少获得赋权图中
某两点之间的最短路以及所包含的边数,这是 8$96:
+.() 算法和 #;-2< 算法无法完成的.
由于使用的是矩阵计算,程序设计简单,得到的
信息很多,因此,本文中所讨论的算法对于很多实际
问题,尤其是对实际 =>? 系统非常有用.实际算例
表明,本算法不但可行,而且非常有效.
使用本文所述矩阵算法,求得的最小费用路径
如表 4 所示.
表#" 实验结果
0%1 ,+2310
起点 @ 终点 最小费用路径
?4:A4 ?4:BC:BD:E4:B4:A!:A4
?4:A! ?4:BC:BD:E4:B4:A!
?4:AD ?4:BC:BD:E4:B!:AD
?4:AF ?4:BG:BH:BF:AH:AF
?4:AH ?4:BG:BH:BF:AH
?4:AG ?4:BG:BH:AG
?4:AI ?4:AI
?4:AC ?4:BC:AC
?4:AJ ?4:BC:BJ:AJ
?4:A43 ?4:BC:BJ:B43:A43
?4:A44 ?4:BC:BJ:B43:E!:B44:A44
?4:A4! ?4:BC:BJ:B43:E!:ED:B4!:A4!
?4:A4D ?4:BC:BJ:B43:E!:ED:B4D:A4D
?4:A4F ?4:BC:BJ:B43:E!:ED:B4D:B4H:A4F
?4:A4H ?4:BC:BJ:B43:E!:ED:B4D:B4H:B4G:A4H
参考文献:
[4]" 邦迪 K A,默蒂 L ? M& 图论及其应用[N]& 吴望名译&
北京:科学出版社,4JCF&
[!]" 严寒冰,刘迎春& 基于 =>? 的城市道路网最短路径算
法探讨[K]& 计算机学报,!333,!D(!):!43:!4H&
[D]" 陈正江,汤国安&"8>=NAO"=>? 软件系统及其应用
[K]& 西北大学学报(自然科学版),!33!,D!(D):!CJ:
!J4&
[F]" 柴登峰,张登容& 前!条最短路径问题的算法及应用
[K]& 浙江大学学报(自然科学版),!33!,DG(H):HD4:
HDF&
[H]" 鲍培明& 距离寻优中 8$96+.() 算法的优化[K]& 计算机
研究与发展,!334,DC(D):D3C:D44&
[G]" BPM'?PQA? 8 O& A +$7,;/ )*< R)+. ;)1/; S-((/S.
($.T7 R-( +T-T+[ K]& U/.V-(6+,4JJD,!D:I3D:
I3J&
[I]" EWPMQA??QX B Y,=Z[8BPM= A Y,MA8\>Q '& ?T-(:
./+. ,).T+T7+:'T/-(2 )*< /0,/($7/
[K]& N).T/7).$S); O(-%()77$*%,4JJG,ID:4!J:4IF&
(编" 辑" 曹大刚)
$4+ %156,-04.2 06 2617+ 246,0+20 *%042 -/ 8+-540 5,%*42
8-04 .%0,-) .+04692
\WAU= [/$
(8/,)(.7/*. -R E-7,^./( ?S$/*S/,U-(.TV/+. L*$]/(+$.2,_$')* I433GJ,ET$*))
:&20,%;0::-." ?-7/T7+ .- R$*< .T/ +T-T+ $* V/$%T./< %(),T+04692" B)T/
7).($0 S);S^T/T7+23102" 'T/T7+ $*S;^ .T/ +T-T 1/.V//* )*2 ,)$(+ -R *- .T/ S-R .T/ +T-T $*S;^<$*% 7$*$7^7 /<%/+;.T/T7 .- R$T-T+ 1/.V//* )*2
,)$(+ -R T/T7 .- R$*< .T/ U +T-T+ 1/.V//* )*2 ,)$(+ -R *-6/;132-6/" B/S)^+/ .T/
);%-($.T7+ $* .T/T/ 7).($0 )+ .T/T/R .T/ ,(-%()7 $+ /)+2& Y)R .T/T7 $+
S.$S/+&
?+@ 86,92:7).($0;V/$%T./< %(),T;+T-T
—3DH— 西北大学学报(自然科学版)第DF 卷
万方数据