最短路算法简介_田丰

· 七 , 二 “ 、 、 二 马 , ‘ , . 牡 : : ‘ 一 .二. 最 短 』路 算 法 简 介* 中国科学院数学研究所 ‘ 田 丰 ’实际生活中 , 会经常遇到各种各样的图 , 诸如交通运输图 、线路图和工序流线图等等 . 在图的应用与研究中 , 最短路问题是基本问题之一 ‘ ; 设 ‘ 于 (X , U )是一个有向图 , 其中 X 于 {今 ·。 , 一 , 粉} 是顶点集合 , 、 U 是弧集 合 一和每二弧 (。 , 二 , ) 〔U 相对应有一个长度 l(x i, 二 ,乏_(也简记为 ‘、, ). 若从 “ 到 xi 没有 弧 , 即 (x , , 二i) ‘U , 则令 lii 一 + 卯 , 又对 i 一 ,1 , 2 , ⋯ , N , 令 lii’ 一 Q. . . 所谓从 幻 . 到 x i* 的一条路 , 是指 G 中的一个顶点序列 产 一 {x 。, 为 : , ⋯ , xi , }(其中点 可以重复 ), 使 (x i , 二* ‘+ , ) 任 U (t ~ 1 , 2 , 一 , 友一 1) ; 特别地 , 若 二 ‘一 为砂 则称之为回路 . 我们把路 产 上的所有弧的长度之和 , 即 路的长度 . 艺 l(x it , xi t十 : )称为路 ; 的长度 , 相应地定义 回 图 ‘ 中 , 给一个顶点 x , (称为始点 )及顶点 xj (称为终点 ) , 最短路问题就是在所有 从 x ‘到 翔 的路中寻求长度最小的路 . 这样的路称为从 x , 到 xi 的最短路 . 最短路问题可以直接应用于生产实际 , 例如各种管道的铺设 、线路的安排等等 . 另一 方面 , 也被利用来作为解决其它一些问题的工具 , 如输送网络中的最小费用流问题 , 可 以 化成一系列最短路问题去求解叭统筹 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 中的关键路实际上是工序流线图中的最长路x); 近年来 , 也有人把最短路问题应用于解整数规划及某些特殊规划问题中 , 例如〔1。」[ 1 1] . 我们要指出 , 问题 中所说的 “长度 ”是广义的 . 比如 , 在输送网络中 , 从 x 、要输送一个 单位的物资到 为 , 若 “长度” 是指通常意义下的距离则最短路就是使运输距离(公里数)最 小的运输路线 ; 若 “长度 ” 代表输送时间 , 则最短路就是运输时间最短的路线 ; 也可以代表 费用 , 则相应地就是使运输费用最省的路线 . 对于无向图 , 我们把每条边换成两条方向相反的弧 , 每弧的长度等于原来的边长 , 化 成有向图的情况 . 本文介绍两类最短路问题的一些算法 . 有关图的一些术语和记号 , 参考 [ 1] . 第一类问题 从一个始点到一个终点的最短路问题 . 为明确起见 , 设始点是 x l, 终点是 却 . 从下面的算法可以看到 , 最后所得到的实际上 是从始点 x : 到各点的最短路 . 首先考虑所有弧长 右, 非负的情况 . 算法一 : 目前公认的最好算法是由 E . w . Di jks tra 提出的[3] . 方法是给每一个顶点 记一个数(通常称为标号 )—临时性标号 (简称 T 标号 )或者永久性标号(简称 尸标号 ) . * 19 7 4 年 2 月 18 日收到 . 1) 在工序流线图这样一类所谓 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 网络中 , 是不含回路的 . 因此 , 把每弧的长度 l(x , , 朴)换成 一 l(, , , 句) , 下面 介绍的有关算法总是可行的 . T 标号表示从始点到这一点的最短路长度的上界 ; p 标号则是从始点到这一点的最短路 长 . 每一步 , 把某个点的 T 标号改变为 尸标号 , 这样 , 一旦终点得到 尸标号 , 算法停止 . 若寻 求从始点到每丫点的最短路 , 则最多经过 (N 一 l) 步算法停止 . 这里 N 是图的顶点个数 . 开始 , 给始点 二、标上 尸标号 d(x l) 一 0 , 给其它各点标上 T 标号 d(x , ) ~ l。 (i ~ 2 , 3 , ⋯ , N ) .然后 , 在所有 T 标号中选取最小者 , 譬如说 d(x ,0) 一 lli 。则把点 铆 。 的 T 标号改变为 尸 标号 , 并重新计算具 T 标号的其它各点的 T 标号 : 选点 xi 的 T 标号 d (幻) 与可(x ,0) 十 li’ 中的较小者作为 xi 的新的 T 标号 . 一般地 , 设 尸 一 {x , }x , 具 尸标号 } , T ~ {x ,卜, 具 T 标号}一 X \p . 令 ‘(x , ) = m in {以(x i )} (1 ) 为点 x * 的 p 标号 , 于是 叙 e P. 把 T \毛x价中点 右 的 T 标号修改为 m in {、(x s), J (x * ) + l* s} 、 . } 重复上述步骤 , 直到 二、 。尸(这时 d (xN )是从 二 ; 到 二 N 的最短路长 , 当然汐口果问题只要求 从 x , 到 x N 的最短路 , 那么在编制程序时 , 可安排停机 , 一般会 缩短计算 时 间 . ) 或者 }Pl ~ N 一 1 (这时求得从 x ; 到每一点的最短路长 )或者式 (l) 中 d (叙) ~ + co (这时从 x . 到 T 中各点没有路 , 从而从 x ; 到这些点的最短路长是 + co ) . 算法的正确性是显然的 . 因为在任一步 , 设 尸 中每点的 尸标号是从 x ; 到该点的最短 路长 (开始 p 一 毛二 ; }, 武二 , ) 一 。, 这个假定显然是对的) 那么只要说明按(1 )式 , 武二 , )正 · 是从 朴 到 叙 的最短路长就行了 · 事实上 , 任尸条从 xl 到 ‘ , 的路 , 若通过 T 的第一个点 是 二 , , 而 劣 , 铸 叙 的话 , 由于所有弧长非负 , 则这种路的长度不会比 d(叔 )小 . 为了编制计算机程序的方便 , 也可以把开始时各点的 T 标号标为 + co (见框图) . 友友= lll 户户~ 111 对对 x ‘〔TTT ddd( x ‘ ) = m i n {d ( x , ) , d( x , ) + l , 滚 }}} ‘‘一 那爵 [d (x ‘)]]] ppp 记人取该最小值的第一个下标 i JJJ { J r 二 : 、= o !匕二竺二竺军立匕上二习. 今 ‘ · 一 } T 一 {二 ! , ! 3 , ⋯ , X 、 } } 各 } * 一 , ! 杏 一一匀卜一一产 之 产 心 亡 <工不获瓤百万万>堡 杏非 1 : 一 T \{X , } } 杏 左= 左+ l 算 法 一 框 图 例 1 . 图一中 , 每弧旁边的数字表示弧长 , 这时图的长度矩阵 L ~ (l; , )为 coco88 ,土内j02 2411/0凡j1 CO 00cocoo ,J曰八” 口一2 02400 0cocos8coz才了11‘es..ll、、 利用算法一寻求从 x , 到各点的最短路长 , 每一步结果 如下 : 女 l 集 合 T 标 号 (d ( x ‘)) {x : , x 3 , x ‘, x , , x 。} { x 3 , x ; , x , , x 6 } {x 3 , x , , 二‘ } 一井卜上竺上一一一〕 l 飞x ‘J ( o , l , OQ , 2 , co , co ) ( 0 , l , 4 , 2 , co , co ) ( 0 , l , 4 , 2 , 5 , co ) (0 , l , 峪, 2 , 5 , co ) (0 , 1 , 斗, 2 , 5 , oo ) 故从 二 : 到 朴 , 介 , 石 , x , 的最短路长分别 为 1 , 4 , 2 , 5 而从 x , 到 x 。没有路 . 现在考虑一般情况 , 即允许弧长小于零 , 这时 , 我们要附加一个限制 , 假定图中不含有 长度小于零的回路 (负回路 ) . 这个假定是很自然的 , 因为图中若含负回路 , 则最短路长可 能是没有下界的 . 对于无向图 , 要求边长非负 . 在下面的算法 中 , 或者求得最姐路 , 或者指出图中含有 负回路 . 易见 , 当图中有负长度的弧时 , 算法一是行不通的 . 这 从图二的例子 中可以看到 . 根据算法一 , 从 x : 到 x 3 的最短 路是 {二 , , 二 3}长度为 1 , 而实际上应是 {二 1 , 二 2, 二 3 }, 长度为 一 2 。 设 d ( x , ) 是从 x , 到 x , 的最短路长 , 根据动 态 规 划原 理 , d ( , , ) 是下述方程组的解 : 、,、了、2 ,‘,J矛‘‘了、、d ( x , ) 一 mi n [ d ( x 、) + l,j] , ( i ~ l , 2 , ⋯ , N ) . !为了求得 ( 2 )的解 , 我们可以利用如下的迭代公式 , 对 左~ 2 , 3 , ⋯ ⋯ J‘左, ( x , ) 一 m.i n 一 [ d“ 一‘义x ; ) 十 l, , ] , (护= l , ⋯ , N ) . 初始条件为 d “ ,( x , ) = z; , , ( i 一 1 , ⋯ , N ) . ( 3 ) 式中 d( 习( x , ) 是第 友一 1 次迭代的值 , 可以理解为从 二 ; 到 x , 的包含不 多于 友条 弧的最短路长二 :当迭代过程收敛 , 即对所有 j, d ‘“, ( x , ) = “乏一 工,( x j) 时算法停 止 , J‘七, ( x i ) 是从 x , 到x , 的最短路长 . 因为从 x , 到任一点的最短路包含至多 (N 一 l) 条弧 (若图 中不 含 负回路) , 故当 友一 N 时 , 或者收敛 , 或者表明图中含有负回路 . _ _ _ 易见 , 在这个算法中 , 反复地修改各点的标号 (如果可能的话) . 和算法一不一样 , 在 算法停止之前 , 每一点的标号都未必是最后的二 我们注意到 , 这个迭代过程的每一步 , 计算各点的标号时 , 所利用的只是前一步的标 号信息 , 因此 , 一个稍稍不 同的算法就是按照 i ~ 1 , 2 , ⋯ , N 的顺序 , 计算 d( 妇(xi )时 , 把 、(“,(x ‘) (i < i) 利用起来 , 即 : ‘ ““,(x , ) 一 m ‘n {兜 [“互,(X ‘) + ‘萝, ] , 灌梦[ ‘(‘一‘’(x ‘) + “‘] }· 我们推荐 J. Y . Ye n . 进一步改进了的算法 . 算法二 : ‘ 利用如下的迭代公式去求得(2 )的解〔们 : 一 ” , d( 的(xi ) 一 气, (i ~ 1 , 2 , ⋯ , N ). 对 友一 1 , 3 , , , · ·⋯⋯“七, (‘,夕一‘n 愁份:n (“友, (x 、) + ‘、, ) , ““一 ‘, (x 夕)} (j一 ‘, 2 , 一N )对友一 2 , 4 , 6 , ⋯ ⋯ (4 ) d ‘七, (x , )一 m in {君尹(d ‘左,(x ‘) + l‘, ) , ‘ d ‘弋一 ‘,(x , ) } (j一 N , N 一 1 , 一 2 , l) 、同样地 , 当所有 d( 习(x , ) ~ d( 七一 ‘)(x ; ) 时算法停止 . 而当 咬一 N 时若不收敛 , 则图中含负 回路 . 刃算法二是交替地向前和向后地去计算各点的标号 , 充分利用各点的新标号 . 这个算 法的计算量大致是公式(3 )所需要的计算量的一半 . 我们在 D Js一21 计算机上用 自动化语 言程序计算一个 48 个点的无向图的最短路问题 , 按公式 (3 ) , 当 左~ 12 时收敛 (花费四分 多钟) , 而按公式价) , 当 天一 6 时收敛 (花费不到两分钟) . ddd :(二‘) = l : ‘. 1 , 1 , 2 , ⋯ , NNN l · 一下钾万弓、 按 护= l , 2 , ⋯ 。 N 的顺序 按 护二 N , N 一 1 , ⋯ 2 , 1 的顺序 d : ( x , )一 m in {d l(x ,) ,哭尹[d Z(x ‘)+ l‘, ] } d : (‘ , )一 , ‘n {沙1(X , ) , !忠尸「d :(x ‘) + “;〕} 瑟薪六导乡目一星争吓而不不不万{ l ,—}d ·(X ,)一 d 正(X ,) 7一‘, ⋯ , N }算 法 二 框 图例 2 . 求图三中从 x : 到各点的最短路长 . 按算法二 , 计算结果如下 : 不含负回路 , 现若把 x 、加入 是 互~ o , (d ‘。,(x i)) 七 (o , l, co , 2 , co , co ): 左~ l乡 (d “ ,(x j)) ~ (0 , l, 4 , 一 3 , o , 印 ); 互~ 2 , (d ‘, ,(x , )) = (0 , 1 , 2 , 一 3 , o , OQ ); 反~ 3 , (d ‘, ,(x , )) 一 (d ‘, ,(, i)) . 算法三 : G. B . D an tz ig 等人提 出 另 一种 思 路 的 算 法 〔5 , . 设 X * 是图中某 左个点的集合 , 由 X * 生成的子图记为 仇 . 算法从 左~ 1 , X , ~ {x , }开始 , 逐步地扩大 X * , 计算 出 G * 中从 x , 到各点的最短路长 . 当 、左~ N , x 、 一 x 时 , 算法停止 . 设 d( U (补)是 G * 中从 x , 到 xi 的最短路长 . 假设 ‘冲 X * , X * + : = . X * U 毛x ‘}, 那么 , G * + ; 中从 二 , 到 x , 的最短路长 d“ + , ’(x , ) 然后开始一个小的计算子过程 , 一 m in {己‘左, (二 , ) + l, ‘} . (5 ) x 矛‘ X 乏 就是要计算 G 好 ; 中从 x ; 到每一点 右(〔 x 户的最短 路长 d( 针‘)(xi ) . 这可以利用类似算法一的方法去进行 . 开始令 X * 中每一点 xi 的 临 时 性标号 d ‘互+ ‘,(x , ) 为 d ‘七, (x , ), 即 d ‘七+ ‘, (x i) 一 d伏 , (二i). 设 p 是 G * + , 中具永 久性标号 d( 针叹x , ) 的点集合 , x : 是子过程中前一步刚加入 p 的点 (子过程开始时 , 尸一 {x 、}, x : ~ 价 ), 则把 X *切 中点 有 的临时性标号修改为 口‘花+ 。’(二, ) ~ m in {d( 七+ 1) (x , ), . 子左+ 劝(x , ) + l‘s} , 设 x , 。是使 {d ‘无+ 。’(x s) 一 d ‘左, (x i)} (x s 〔X *\P )取最小的点 , 即 : J‘“+ 。‘(x s 。 ) 一 d ‘互,(x , 。) 一 分两种情况 : 】1l ln x少‘X 搜\尸 {J(七+ , ,‘ ( x i)一 J‘“, (x , ) }. 1 “ . 若 了针坎(x , 。) 一 了妇(右。) < 0 , 则把点 气 的临时性标号修改为永久性标号 , 即把 为 。加入 P, 重复上述步骤 . 2 “ . 若 、‘“+ ”’(x , 。) 一 、‘“, (x ,。) 一 。, 则对所有 二 , ‘ X ,\P , 这时的临时性标号均修改为 永久性标号 . 子过程结束 . 因此 , 这个子过程进行到或者 }川 ~ 左或者情况 2 “ 出现 . 为了检查子图 G 卜 1 中含负回路的可能性 , 子过程中每当增加一点—例如 气—进人 尸, 需要检查如下不等式 : 己“ + l) (二 , ) > d ‘七+ , , (x , 。) + l, 。* 是否成立 (这里 x ‘是子过程开始时加入 X , 的点) . 若成立 , 则 ‘杆 : 中含负回路 , 从而整 个计算过程结束 . 根据上述迭代过程 , 我们可以按 左~ 1 , 2 , ⋯ , N 的顺序 , 开始 x l一 {x , }, d( l)( 二 1)一。, 逐步地把 叙 增加到由 X 卜 1 ~ {朴, 朴 , ⋯ , 八一 : }生成的子图 ‘卜 ; 中 . 直到 交一 N 时为止 . 例 3 . 以图三为例 , 算法三的每一步结果为 友一 l , (o ) ; 左= 2 , (o , l)毒 晚一 3 , (0 , 1 , 钓 ; - 反产 4 , 一 (o , 1 , 4 , 一 3 ) ; 反一 5 , (o , 1 , 4 , 一 3 , o ) ; 左一 6 , (0, 1、 2 , 一 3 , 0 , co ) . 在 D JS 一21 、计算机上 , 利用本算法计算 48 个点的最短路问题约一分半钟 , 利用算法 一要一分钟 . 左左= 222 对对 x , ( TTT ddd : ( x , ) 二 m in {d Z(x , ) + 止, , , d : (x ,) }}} SSS 一界爵 [d Z(’ , ) 一 J l(r , )] --- PPP记人达到上极小值的第一个下标 萝萝 图图 中 含 负 回 路路 打打印 d : (x , ))) zzz 二 l , 2 , ⋯, NNN TTT 二 T \{ x , }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} ddddddddddddddddd : ( 二‘ ) = d : ( x ‘ ) i二 1 , ⋯ , 左左 犷犷 = r + lllllllllllllll 左左左左左左左左左= 左十 lll 算 法 三 框 图 第二类问题 从任一点到另外任一点的所有最短路问题 . 介绍两个同样有效的方法 . 算法四 : 是由 R. w · Fl oy d 以 Al go l语言程序形式发表的“〕. 方法是从 D( 0) ~ (气) 出发 , 依次构造出 N 个矩阵 D ‘, ) , 刀‘, , , ⋯ 。 D ‘N , . 第 及个矩阵 D 伏, 一 (d梦, )的元素 口分, 表 示从 x , 到 x , , 而中间点仅属于从 x ; 到 叙 的 反个点的所有路中的最短路长 . 已知 。‘“一。 ~ (‘{夕一 ‘,), 第 反个矩阵 D ‘左, ~ (d梦,) 定义如下 : dl; , 一 m in {d {;一 。 , d l迄一 , , + d诱一。} , (6 ) 计算过程从 友‘ 1 开始 , 让 i , j分别取遍从 1 到 N 的所有值 , 然后 硬增加 1 , 反复进行 , 直 到 左~ N 时终止 . 这时 D( N) 一 (拼笋) 的元素 研尸就是从 x ‘到 x , 的最短路长 . 从 (6 )式可见 , 当 难一 1) (或 d铸一l)) 为co 时 , 则 D( 习 的第 i 行就是 D( 七一l) 的第 i 应地第 夕列不变 )从而减小计算量 . 此外 , 若令 乙, 一 + co (‘一 1 , 2 , ⋯ , N )则 斑户表示图中过 x ‘的最短回路长 . 含负弧长的图 , 若 li ; 一 。, 而在第 左步 , 武乒, < o , 则表明有负回路通过 幻 . 例 4 . 用算法四计算图三的所有最短路长 , 行(相 对于 800coco0 1 一 2 0 0 0 (幻 一 1 一3 0 一 4 一 1 一 5 一 2 80 内‘†on ” 2„弓j 0 .一一 ,占0lfZ22 88 0 0 1 了矛了.J‘......、、、、 一一D l } * 一 1 } l -—} ! 一 1 . }l— -一一《 或 肉< + col是} , 一 ‘ } >‘进止-_ _ ’仁 _ 、 月。盯-一 ) , 《二亚三三 )一⋯ 一 ,应壶困 { 旦 一 l !三三口一君- <二二三二卜— 「一一一一一一一一, 一 是 /—、一 } ‘ 二 ‘ + ‘ !—一火 ‘ < N Z一一1。。万一一一一二二一‘一份 、 · 月卜“-一一~ - 一1女 所 有 J“ 理 “ 少一一} 图 中 含 负 回 路 1}是一阵不刃二之<宁不石一>l、卜 1 打 印 ( d 应, ) } 算 _法 四 框 图 算法五 : G. B 4 8 Da nt z ig 根据和算法三同样的思路 , 即求出一系列维数逐步扩大的矩 阵 D 诈, , 它表示在由 X , ~ 行 ; , 朴 , ·⋯ , 二、乡生成的子图 G 友中每一对点之间的最短路长 , 提出如下的算法 [7] . 开始 D (‘) ~ (o )l、 1 , 已知 (左 x 左)的矩阵 。‘七, , 定义 D ‘互+ , , 如下 : (1 ) 对 i = 一, 2 , ⋯ , 左, 武洲 一器畔 , +l 。诚 : d粼{l‘ m in [ z、、 ; . 、 + ‘:乒, ] ; l鉴户巨女 , (2 ) J狱 :飞+ , ~ 。in {o , m in [ d狱 :} + d {绪{]} ; 1鉴j舀女 (3 ) 对 i = 1 , 2 , ⋯ , 友, i = 1 , · 2 , ⋯ , 反, .礴{; + ‘, = m in [ dl; , , d , :迄丰}, + d狱 :}] ; 算法进行到某一步 , 若 沙澎之 0, 说明图中出现负回路 . r 例 5 . 按算法五计算图三的例子 , 每一步结果如下 : 左= 1 , (O) ; 、一 2 , (叩 、、les,eel./月,,jŽU0cosz‘矛了.且、、、 ,j一一.户、” 一 1 0 4 7 一 3 一 4 一 5) 0888 口了布口.......、、、 乙.一一,左‘ 一 3 一 4 一 5 一 1 一 2 、、、llwe|JJ121|/cosco8coo ,‘月,一 o一·一300 . O 一 3 一 3 一斗 一 5 0 一 3 一 3 0 .闪co一88/⋯、、尸。,J 。。一、2一一,夕 左= 6 之二二 n l l n 1昌j舀 赴~ l [d ‘户+ l, 。] 二二 n l l n 且含子昌在一 1 [ l* ) + d , , ] 话妇dd , ⋯ , 左一 1 , 护= 1 , 2 , ⋯ , 及一 1 d ,沪 = m in [d , , , d , 龙 + d 。 ,」 对 算 法 五 框 图 最后简单介绍一下如何求得具体的最短路线的问题 . 、这里有两个途 径是可 以 利用 的 . 一个途径是与计算最短路长的迭代过程同时 , 记录最短路线 . 例如算法一中 , 每 当 d (xi ) 由沙(x , ) 十 li ‘取值时, 则与记录 d (xi )的值同时 , 记录 下点 二 , . 迭代过程终结时 , 若与 二 , 相应所记录下的点是 二 , , 则从 二 , 到 二 , 的最短路线的最 后一条弧是 (二 , , 二 *), 再根据 二 , 相应的记录点, 找出最后第二条弧 , 如此一直到 二 , 时为 止 . 又如算法四中 , 与 D( 习 迭代的同时 , 计算一个路线矩阵 R( 划 . 开始 R( 。, ~ (; 纷) , 其中 r ll , ~ j(i , j一 l , 2 , ⋯ , N ) , 它的迭代公式是 : 若 可; 一1) > 叫委一。 十 d矫一l,; , 若 磷少一。 基 磷类一。 十 d矫一代一‘气·了 石飞rr . l.之.we.‘ 一一L分 . . ] r 根据 R( N , 就可以找出从一点到另一点的最短路线来 . 例 6 . 对于图三 , . 5 0 、、、、J11|||了声/zJ5 2 4 6 5 斗 斗 6 3 4 2242卜44 偏甲: ,工11,1,11111//矛||l卜厂t、、 一一齐义R (6 ) 4 6 5 _碑 乡 冷 一 , 3 3 4 由 ,帝, ~ 4 , 又 ; 护 ~ 3 , 嵌从二‘勤二 2的最走菇线是凤 x 3 , x ; , x Z } 另一个途径就是计算出最短路长之后 , 根据每点的标号 d (xi ) , 寻求使 d(x , ) + 乙, ~ 武万)的弧,.(, 禹)二二 ;杯这释的弧为基苯弧 . 由所肴甚本弧生成的部分图中 ,从始点· 二 ; 到 扩的任一条路都是到该点的最短路 . 例如一自兰中所有的粗弧就是基术弧少 ‘ , · 旅 ’二关于篡镜路问题及有关方面的概述 , 见 〔8 ] , 夕对手具特殊结构的大型图可利用分解寞瘾蜷考[9J 于 , ’ ; 一 扮 : · 一 ‘· 、 一 、 . , 、参 ‘ 一考 一 资 , ,火料 贝尔热 C . , 图的理论及其应用 , 卫o r d L . R . , J r . , 卫u lk e r so n D ijk str a E . W . , A N o t p q p 饥a 亡乞无, 1 (1 9 5 9 ) , 2 6 9一2 7 1 . J in Y . T 明, _ A n A lg or i幼1困 李修睦译 , 科学技术出版社 , ’上海 , 1 9 6 3 , D . R . , F Zo 叨s 坛几 T w o P r o ble m in N e t‘o r论s , p r in “et o n , 1 9乒仑· C o n n e x io n 杭th G r a p h s , 叮似饥即‘s c h e M压才h 6 · n o d e s to a 9 1, e n D e stin a tio n . in q en e r a l N e tw ‘ D a n tz ig 0 . B . , 它la ttn er w : ’ G r a p h , 全h百o r 艺e d es 召, 怀Ph es , 卫loy d R . W . , A lg o r ithm . 9 7 , ￡o r ‘r 认4认g s ho r test · R o u te s F r o m A ll 5 0 , r k 影、 Q , a r声: 卢 ””l· 脚 th ., 2 7 : 4 、(1 9了o )· 0 . , ‘ R 垃0 M . R . , A ll S h o r te st R o u t e3 ‘ f r o m a fix e d o r i宫饭 in ‘a ,J ., .J, .J, .J, .J,土O自n口连一.”勺r.r.L.”.LL昌L,一..L R o hi e , 1 9 6 6 , 8 5一9 0 . _ S h o r t e s t P 拜t五, C o 饥饥 . A C皿. , 5 (1 9 6 2 ) , : 3 4 5 . [ 9 ] [1 0〕 D a n t z i g G . B . , A zl sh o r t e st ‘ R o u t e s in a e r a p h , r 几‘南 e d e s ‘:叩 h e : , R o m e , i 甘6 6 , 9 1一9 2 . D r e y f u s 5 . E . , A ll J 人p p r a i sal o f , S o m e 『 S h o r t e st ·p a th A lg o r i th m s , 口p e . 五 e s , , 1 7 (1 9 6 9 ) ; 3 9 5一 4 1 2 . H u T . C . , A D e e om p o s i t i o n A lg o r i thm fo r Sh o r t e s t P a tll s i n a N 亡俪o r k , Op e . ’ 五℃5 . , 1 6 ( 1 9 6 5 ) , 9 1一1 0 2 . S h a P i r o J . F . , D 丁n a m ie P r o g r a m m in g A lg o r i th m s f o r th e I n t e g e r P r o g r a m m i n g P r o b le m-- I : T h e 工n t e g e r ’ P r o g r a m m i n g p r ob lem v i e w e d a s ’a K n a p sa e k 切 p e P r ob l.om , o , e . 五e : . , ’1 6 ( 1 9 6 5 ) , [s][7][s] [ 1 1 ] 1 0 3一1 2 1 . 飞 :卿· ‘E · 严 “卿rP. 旦 .R,. A气业吧戮乃 e 吕U u r C e 七o n 吕L r 蕊 U LL日, 雌 0 , ‘. O C 番一 , l ‘ : 上乙 、1 沙 了i ) , fo r 0 P t加a l P r o je e t S ( , h e d ul i n g u n d e r M u lt iP拓8 0 3一8 1 6 - 5 1