（计算数学专业论文）网络容量扩张问题研究.pdf

a b s t r a c t t h en e t w o r kc a p a c i t ye x p a n s i o np r o b l e mi sac l a s s i cp r o b l e mi no p e r a t i o n sr e s e a r c h i ti sc l o s e l y r e l a t e dt or e a ll i f ea n dh a sa s t r o n gt h e o r ya n dr e a l i t yb a c k g r o u n d t h ek n o w l e d g eo fn e t w o r kc a p a c i t y e x p a n s i o ni sw i d e l yu s e di nt r a n s f o r m a t i o no fu r b a nt r a n s p o r tn e t w o r k ，p o w e rn e t w o r ku p g r a d e ，a n d c o m m u n i c a t i o nn e t w o r ko p t i m i z a t i o ne t c t h i sc h a p t e ri n t r o d u c e st h eb a s i ck n o w l e d g eo fn e t w o r kc a p a c i t ye x p a n s i o np r o b l e ma n dg i v e s s o m ec l a s s i cm o d e l s t h e s em o d e l sa r eb a s e do nd i f f e r e n tn e t w o r kc a p a c i t yd e f i n i t i o n s i nz h a n g j i a n 。z h o n ga n dy a n gc h a o sm o d e l ，t h en e t w o r kc a p a c i t yi sd e f i n e da st h em a x i m u mc a p a c i t yo ft h e n e t w o r ks p a n n i n gt r e e ，w h i l et h ec a p a c i t yo ft h es p a n n i n gt r e ei sd e f i n e da st h es m a l l e s te d g ec a p a c i t y o nt h et r e e t h e i rm o d e li s h i g h l ye f f e c t i v e ，t h e r e f o r et h ed e f i n i t i o nm e t h o dh a v eb e e nq u o t e d e x t e n s i v e l y s t o c h a s t i cm o d e li sar e s e a r c hf o c u s ，w h i c hr e l a t e dt os t o c h a s t i cc o s t ，s t o c h a s t i cd e m a n d ， s t o c h a s t i cr o u t ec h o i c ea n do t h e ru n c e r t a i n t i e s i ti sav e r yb r o a ds t u d yf i e l d t h es e c o n dc h a p t e rg i v e san e t w o r kc a p a c i t ye x p a n s i o nm o d e lo nd e m a n d i nac o n n e c t e da n d u n d i r e c t e dn e t w o r k ，t h ef l o wp a t hb e t w e e nt w op o i n t si sd e f i n e da st h es h o r t e s tp a t hb e t w e e nt h e m e v e r yf l o wp a t hb e t w e e na n yt w op o i n t sh a saf l o wd e m a n d i nt h en e t w o r k ，e v e r ya r c sc a p a c i t ym u s t n ol e s st h a nt h et o t a ld e m a n d so ft h ee n t i r ef l o wp a t h sw h i c hi n c l u d et h i sa r c o t h e r w i s e ，t h i sa r c s c a p a c i t yn e e d st ob ee x p a n d e d s u p p o s et h a tt h ec o s to fe v e r ye x p a n d i n gs c h e m ei sal i n e a ri n c r e a s i n g f u n c t i o no ft h ee x p a n d i n gc a p a c i t y , ap o l y n o m i a ls o l u t i o na l g o r i t h mi sg i v e ni nt h i sa r t i c l et om a k et h e a r c sc a p a c i t yi nt h en e t w o r km e e tt h et o t a ld e m a n d sa n dh a v et h em i n i m u mc o s t t h i sa r t i c l ec o n s i d e r s t w oc a s e so ft h es h o r t e s tp a t h ：( 1 ) t h e r ei s n td e l a yo nn o d e s t h a ti st h en u m b e ro fn o d e so nt h ep a t h h a sn oe f f e c to nt h el e n g t ho ft h ep a t h ；( 2 ) t h e r ei sd e l a yo nn o d e s t h a ti st h en o d e sh a v ed e l a ye f f e c t s o nf l o w , t h u sn e e dt oc o n s i d e rt h e i m p a c to np a t hl e n g t h i nt h es e c o n dc a s e ，w ei m p r o v e dt h e f l o y d w a r s h a l la l g o r i t h ma c c o r d i n gt ot h en e e d ，a n dg i v ean e wf w ea l g o r i t h m t h et h i r dc h a p t e rc o n s i d e r st h er a n d o m n e s so ft h er o u t ec h o i c et od e t e r m i n et h ef l o wp a t h t h e r e a r eal o to ff a c t o r st oa f f e c tt h er o u t ec h o i c e ，i nw h i c ht h ed e l a yo fn o d e sa n du n c e r t a i ne v e n t s ( s u c ha s e m e r g e n c i e s ) o na r c sh a si m p o r t a n te f f e c t t h eu n c e r t a i n t yo ft h ee v e n t so na r c sl e a d st ot h e r a n d o m n e s so ft h ep a t hc h o s e n t h i sp a p e rg i v e st h e c o r r e s p o n d i n gm o d e lo ft h ep r o b l e m ，a n d i m p r o v e st h ea l g o r i t h mi nt h es e c o n dc h a p t e rt os o l v et h ep r o b l e me f f e c t i v e l y k e yw o r d s ：n e t w o r kc a p a c i t ye x p a n s i o n ；t h es h o r t e s tp a t h ；d e l a y ；s t o c h a s t i cm o d e l 目录 引言。1 第一章网络容量扩张的基本知识及经典模型3 1 1 基本知识3 1 2 基于网络支撑树的容量扩张模型3 1 3 随机模型5 1 3 。1 需求随机模型5 1 3 2 费用随机模型7 第二章网络容量按需扩张模型9 2 1 网络容量按需扩张模型9 2 1 1 问题的定义9 2 1 2 模型的建立9 2 1 3 算法及复杂性分析1 1 2 1 4 算例”13 2 2 节点有阻滞的网络容量按需扩张模型”1 5 2 2 1 新的定义及算法”1 6 2 2 2 算例“18 第三章网络容量扩张随机模型2 0 3 1 路径选择的随机性问题的提出”2 0 3 1 1 问题的定义2 0 3 1 2 算例2 0 3 2 事故概率随容量变化的扩张模型2 2 3 2 1 路径期望优化模型2 2 3 2 2 路径选择随机模型2 3 结论2 8 参考文献2 9 攻读学位期间的研究成果3 2 致谢3 3 学位论文独创性声明、学位论文知识产权权属声明3 4 引言 引言 在现实世界中存在着大量的网络，如交通网络、电力网络、城市供水供气网络以 及物流网络等等。随着社会经济的发展，原有的网络将难以满足增长的需求，因此必 然面临网络容量扩张的问题。例如，对于交通网络中的某条线路，其宽度已经难以满足 出行的需求，因此需要对其进行容量扩张。 我们在讨论容量扩张问题时，不仅要考虑提高流量，更要考虑解决问题的费用， 实际上许多问题要考虑费用问题。例如上面的交通网络容量扩张问题，要想解决这个 问题，需要将马路拓宽，马路每拓宽一个单位需要花一定量的钱，而政府的预算是有 限度的，这里我们考虑如何在费用尽可能少的的情况下提高各边的流量从而使整个网 络的流量达到最大。网络容量扩张问题是图论领域中的一个重要问题，在许多生产实 际中都有极强的应用背景，尤其与近年的物流管理、证券投资、经济发展等领域有较 密切的关系，并在电子通讯等其它许多领域有着十分广泛的应用。 在过去几年中，在网络容量扩张方面，很多专家做了相应的工作。文献 1 】中，r a v i n d r a k a h u j a 和j a m e sb o r l i n 在网络流和网络流模型领域做了相当多的工作，他们给出了有 约束限制的最大流问题的网络容量扩张的算法。文献 2 】中，o b e r m a n 研究了减少一个 给定树的边用来减少最短树的权值的问题，并证明该问题有强多项式解法。文献 3 】中， s o k r u m k e 给出了两个改进的网络流模型，并对一些网络改进问题给出了启发式算法。 文献 4 中，张建中和杨超对一类网络瓶颈扩张问题给出了强多项式算法，他们的网络 支撑树模型是最具代表性的一类网络容量扩张静态模型，其成果被大量引用。在张建 中的研究基础上，杨超等在文献 5 】中考虑了预算和瓶颈容量限制下的网络扩张问题，同 样地给出了多项式的算法。文献 6 7 】中，王洪国等将杨超等的网络瓶颈模型加以扩张， 解决了无向网络容量扩张和有向网络容量扩张的问题，他们进入了固定扩张费用的概 念。文献 8 】中，杨晓光在网络扩张的过程中，引入了多个范式的问题，巧妙地构造了网络 模型来解决网络优化问题，并给出了相应的算法。 最早开始研究机会约束模型的是c h a m e s 和c o o p e r ，他们在文献 9 】中提出了第 二类随机规划，其显著特点是机会约束条件至少以一定的置信水平成立。随后有很多人 开始针对该问题的研究。文献 1 0 中，l i ub 在文献 9 】的基础上改进并给出了相关机会 规划的算法。文献 1 1 】中，a r i n g h i e r ir 将相关机会规划应用到整数规划领域中，并给 出了相应的启发式算法。开始将随机瓶颈容量扩张问题引入的是h i s h i i & n i s h i d a ，见 文献 1 2 】，随后很多人做了相应的工作。文献 1 3 】中，h k a t a g i r i ，h i s h i i 讨论了在模糊 随机边权值下的瓶颈支撑树的机会约束模型。接着在此基础上，h i d e k ik a t a g i r i ， m a s a t o s h is a r a w a k 在文献 1 4 】中研究了模糊随机瓶颈支撑树问题的必要的概率和评估 问题。国内，刘宝碇等在文献 1 5 】中用遗传算法来解决相关机会规划的网络优化中定位 的问题，取得了良好的效果。 青岛人学硕十学位论文 文献 16 18 中，吴云、周建、杨郡首次提出了网络瓶颈容量扩张问题的通用机会 约束规划模型，建立起通用的模型和解法，并首次在随机网络瓶颈容量扩张问题中提出 通用混合智能算法，将网络瓶颈容量扩张算法、神经网络、遗传算法、随机模拟算法集 合在起，有效地解决了该类问题。文献 1 9 中，吴云、林毅、杨超提出了多阶段网络 容量瓶颈扩张问题，给出了该问题的数学模型和算法。他们的研究成果对本文的模型有 很好的启发作用。 本文第一章介绍了关于网络容量扩张的一些基本知识以及几种基于不同的网络容 量定义下的扩张模型，包括张建中和杨超等的网络支撑树模型、吴云和周建等的费用 随机性模型以及何波和杨超等的需求随机性模型。 第二章在前面研究的基础上，借鉴何波和杨超等的需求随机性模型，进一步提出 了网络容量按需扩张的模型。其中对文献 3 3 】中f l o y d w a r s h a l l 算法的引用很好的解 决了寻求任意两点之间最短路的问题，使得任意两点之间的流量路径得以确定。在实 际中，对同一个网络容量扩张问题，有多种扩张方案可供选择，这罩将每种扩张方案 的扩张费用定义为关于扩张容量的函数。本章给出了解决该问题的一个复杂性为o ( n 3 ) 的多项式时间算法，使得各边容量达到需求，且总的扩张费用最小。另外，考虑了节 点的阻滞对网络流的延时作用，将其等效为对路径长度的影响，根据需要对f l o y d w a r s h a l l 算法做了改进，生成新的f w e 算法。 第三章主要研究了路径选择的随机性对容量扩张决策的影响，并建立模型。此处 将影响路径选择的随机性因素考虑为节点的阻滞作用以及弧上不确定事件( 例如突发 事件) 的阻滞作用，而弧上阻滞因素的不确定性必然导致了路径选择的随机性。本章 考虑弧上的不确定事件以一定的概率出现，给出概率随容量变化的函数，进一步改进 算法，有效地解决了该问题。 2 篁二童堕笪查量芏整塑茎奎型望星丝壅堡型 - _ _ _ _ - _ _ _ _ _ _ _ _ _ - _ - _ _ _ _ _ _ - _ _ - _ _ _ - - _ _ - - - _ _ 一一 第一章网络容量扩张的基本知识及经典模型 1 1 基本知识 网络容量扩张问题是一类应用极为广泛的网络优化问题，它的形式多种多样，现实 生活中也有许许多多的实例，例如，一个运输网络可能要提高流量，一个生产系统可能 要加强生产能力。在网络容量扩张模型中，决策变量多种多样，有确定变量，也有随机 变量。根据决策变量的特征，我们将网络容量扩张问题的模型分为两类：静态模型与动 态模型。 在近几年关于网络容量扩张问题的研究中，张建中、杨超等的网络支撑树模型是最 具代表性的一类静态模型，其研究成果包含了运用有限的预算费用使网络容量扩张到最 大的强多项式算法；动态模型主要是各种随机模型，包括费用随机模型、需求随机模型 等，本文研究了影响路径选择的随机性因素，并给出了一种新的随机模型一路径选择随 机模型。 1 2 基于网络支撑树的容量扩张模型 么： 图1 1 网络支撑树 如图1 1 ，给出网络图g ( e ，v ，c ，) ，其中v = 1 ，i ，叱，屹 为顶点集， e = p ；，p ：，) 为边集，c r ”为容量向量， r ”为费用向量，用f 表示g 的所有 支撑树组成的集合，向量c 的分量q 以及向量的分量w 分别对应着e 中元素q 的容量 以及每提高一单位p ，的容量q 所需要的费用。对f 中的每一个元素t ，定义其瓶颈容量 ( 即丁中所有边容量的最小值) 为丁的容量，记为c a p ( t ，c ) ，即： 青岛大学硕士学位论文 定义f 的容量： c a p ( t ，c ) = m i nc ( e ) g 1 却( i ，c ) = m a x c a p ( t ，c ) iv t f 对一个给定的容量向量c ，找出f 中的支撑树丁，s j c a p ( t + , c ) = c a p ( f ，c ) ，即找出 m r 。a f x m 甜i n c ( p ) ，这即为所说的不相关的瓶颈问题。这类问题在许多文献中已被广泛研究。 像瓶颈指派问题，瓶颈支撑树问题。近几年，瓶颈优化问题己被归纳成各种优化模型， 另外，一些瓶颈约束问题，例如： m 7 1 。a f xr a 。i 7 nc ( e )7 1 fc 7 盯w ( p ) dj - 一 、7 e e t 也得到了进一步发展。在这里，w ( e ) 表示集合e 中元素e 的权值或费用。我们注意到， 在以上这些所有的模型中，元素e 的容量是固定不变的。 在网络支撑树模型中考虑如何有效的提高集合e 中一些元素的容量，以使得当提高 容量的总费用不超过一个给定的预算d 时，集合f 的容量尽可能的提高。换一种表达方 式，我们来考虑如下问题： m a xc a p ( i f ，c ) 。f 形。( c - c ) d j 1 一 ic c 在这里，矽= ( w i ，w e ，) r ，其中w ，f - 1 ，m 是q 的容量每提高一单位所需要的费用， c = ( q ，c ：，c 。) 7 代表初始的容量向量。 以上这几个问题在很多情况下都可以碰到，举个例子，它们可能出现在电子通讯和 运输工业中，被用来解决通讯或运输流量问题。假设有一个网络图g ( v ，e ) ，令c 表示e 中每条边的初始容量向量，它可能是边的宽度或级别，表示边的容量每提高一个单位 所需的费用向量。定义网络图g ( v ，e ) 的一个支撑树的容量为该支撑树上所有边的瓶颈 容量( 即该支撑树上容量最小的边的容量) ，定义网络图g ( v ，e ) 的容量为所有支撑树容 量的最大值。由此，该网络中任意两个结点之间的流量至少是该网络的流量。假设总预 算为d ，现在问题转化为如何有效的提高边的容量，以使得在总费用不超出预算的情况 下，整个网络的容量达到最大值。 4 第一章网络容量扩张的基本知识及经典模型 对给定的e ，一c ，4 ，d ，集合f 以及f 的容量定义如上，我们的问题是将容量向量石提 高到c ，使得： ( i ) r ( c c ) d ； ( i i ) c a p ( f ，c ) ，：且 ( i i i ) 厂达到最大值。 令h ( r ) = cc c ，c a p ( f ，c ) ，) ，则问题的模型为： ic 日( ，) 六1 r ( c 一石) d 对给定的r o ，这罩定义了一个权向量z 龟，其分量乙而与e 的元素e i 对应，规定如下： 乃忆 - z o ；若百 现在，问题转化为找出权向量z 吩下的集合f 中的最小权元素。这罩f 中的元素丁的权值 定义为丁中所有边的权值之和，令丁表示f 中的最小权元素，定义向量c 龟如下： 妒：拉若q 酊龟，r c , ， i c ，否则 则c 恼是问题的一个最优解，且解的具体值等于丁响在权向量z 龟下的全部的权值。 张建中等的网络支撑树扩张模型对后来网络容量扩张问题的研究具有深远的影响。 1 3 随机模型 在网络容量扩张动态模型( 即随机模型) 的建立过程中，人们考虑了各种各样的不 确定因素，如路径流量需求的不确定性、费用的不确定性、不同时间段的出行限制等等， 并针对不同的随机因素建立了不同的模型。本章给出需求随机模型以及费用随机模型的 简单介绍。 1 3 1 需求随机模型 需求随机模型是指网络中流量需求的不确定性模型。该模型是由何波、杨超等建立 的，他们在无向网络中给出几条路径，用一组情景描述需求的不确定性，使用两阶段分 解算法首先求出每种情景下需要扩张的边及其扩张容量，然后对所有需要扩张的边取并 青岛大学硕十学位论文 集，需要扩张的边的容量取其最大需求值，最后求出最小的扩张成本。 具体过程如下： 图1 2 需要扩张的k 条线路 给定一个网络g ( y ，e ，c ) ，其中v = h ， 9 2 ，) 是顶点集，e = q ，p ：，) 是边集， c = q ，乞，q ) 是相应边的初始容量，w = w l ，w 2 ，心 是扩张后的容量， f = i ，石，z ) 是相应边的单位扩张成本，在这个网络中有k 条线路p k ( k = 1 ，2 ，k ) 需要扩张( 如图1 2 ) ，有一组情景s ( ，= 1 ，2 ，三) ，令玩表示在情景，下线路k 的需求。 模型如下： m i n m z ( w f q ) 嘞m ，= l ，2 ，l i = 1 c a p ( p k ) = m i n w , 巩，k = l ，2 ，k ；l = 1 ，2 ，l w c i ，i = 1 ，2 ，n 0 ，1 ) ，i = 1 ，2 ，n ；l = 1 ，2 ，l 其中，x , t = 1 表示第i 条边在情景，下需要扩张，否则砀= 0 。 在上面的模型中，可以用一个时间段的需求表示一种情景s ，不同情景下各线路的 需求口。是通过一系列调查统计给出的。此时，可以考虑各种情景以相同的概率出现。 实际上，若从不同的角度对可能出现的情景进行描述，则各种情景出现的概率不尽相同， 因此可以对各情景赋予不同的权重局，7 _ 1 ，2 ，l 来表示概率的差异，此时，约束 z ( 一q ) 五， - m ，l = 1 ，2 ，l 就变成了届z ( w q ) 嘞m ，l = 1 ，2 ，l ， 且 6 第一章网络容量扩张的基本知识及经典模型 l f l , = l 。 ，= i 在该模型的算法中，对所有的k ，查找e p k 且c ( p ) 巩，将其置于集合e 中。最 后，对集合面中的边求z ( 巩- c j ) ，即可求得最优解。 巴e 1 3 2 费用随机模型 费用随机模型，顾名思义，就是在扩张费用不确定的前提下建立的网络容量扩张模 型。费用的不确定性使得我们在解决问题的过程中通常以尽可能减少费用为目标来建立 算法。 图1 3 网络支撑树 在吴云、周建等的模型中，定义网络g ( v ，e ，c ) 中的一个生成树丁的容量c a p ( t ，c ) 为丁中各边的瓶颈容量，与张建中的网络支撑树模型类似，即： c a p ( t ，c ) = m i nc ( e ) ， 用丁表示网络g ( v ，e ，c ) 的最大容量树，即 c a p ( t , c ) = m a x c a p ( t ，c ) ) ， 各边的单位扩张费用向量f 是随机变量，服从一定的概率分布，在此随机单位扩张费用 下，采用混合智能算法对原来的容量向量c = 编，乞，c n ) 进行扩张，使得扩张后的网络 g ( v ，e ，w ) 的最大扩张树的容量唧( 丁，肜) = m a x c a p ( t ，形) ) 满足需求，带有机会约 束条件的扩张费用c o s t ( wf ，c ) 在给定的置信区间口下，且总的扩张费用最小。模型 如下： 青岛人学硕士学位论文 m i nm p r f c o s t ( wf ，c ) m ) 口 w c c a p ( t ，w ) r o 其中，设定随机变量w = ，w 2 ，) 是定义在概率空间( q ，人，p r ) 中的。 问题的解决过程中所采用的混合智能算法是将网络瓶颈容量算法、随机模拟方法、 神经网络以及遗传算法结合在一起所形成的一种通用算法，经过数值实例的检验，具有 很好的准确性。 吴云、周建等的费用随机模型对本文中各扩充方案对应不同的费用函数的思想具有 很好的启发作用。 8 第二章网络容量按需扩张模型 第二章网络容量按需扩张模型 在何波、杨超等的需求随机模型中，只考虑了给定路径的需求以及容量扩张。本章 在前面研究的基础上，考虑无向网络上任意两点之间的路径及其需求。拿城市交通网络 举例，人们趋向于走两点之i 日j 的最短路，且任意两点之f 刚都有交通流量需求，若某条道 路的容量( 即宽度) 达不到需求，则会引发一系列如堵车等交通问题。因此，我们考虑 将最短路作为两点之间的流量路径，在这里运用f l o y d w a r s h a l l 算法求出任意两点之 间的最短路，将每条边的容量需求定义为经过该边的所有流量路径的需求之和，每条边 的单位长度扩张费用为关于扩张容量的线性增函数。 2 1 网络容量扩张模型 2 1 1 问题的定义 给定一个网络g ( v ，e ，c ) ，其中v = h ，屹，) 是顶点集，e = e ie 2 ，o9 e n 是边集， c = c 19 c 2 ，已 是相应边的初始容量，w = w i ，w 2 ， 是扩张后的容量， d = 吐，d 2 ，吃) 是相应边的长度，共有r = 1 9 2 ，t 种扩张方案，z ( x ) 是第f 种扩张方 案的费用函数，是线性增函数，则f , ( w k c k ) 表示对e 。运用第，种扩张方案的单位长度扩 张费用。 这旱的网络容量扩张问题定义为使扩张后的容量w = w l ，w 2 ，) 达到需求，且选 择扩张方案，使总的扩张费用q 最小。 2 1 2 模型的建立 用p o 表示v , ，之间的最短路，即v , 9 之间的流量路径，；，表示该路径的流量需求， 建立如下模型： 9 青岛大学硕十学位论文 n 7 m i n q = z ( 一吒) 以 七= lf = 1 s ， w k c k ， 肌一1 w k 勺颤，k = l ，2 ，疗 t = l j = t + l f 1 ，e k p u 2 1 0 ，否则 7 1 x k , = 1 ，k = 1 ，2 ，玎 t = l x a 0 ，1 ，k = 1 ，2 ，玎，= 1 ，2 ，t 其中= l ，k = 1 ，2 ，刀表示一条边对应一种扩张方案。 定理2 1 对模型( n c e p ) ，定义 肼一l册 w k 牝m a x c k ，o ) ， i = lj = t + l 乩木：f 1 ，z ( 牝c k ) = 1 1 1 i n z ( 牝c k ) l t = ”一，n ， 一10 ，否则 则木，木为模型( n c e p ) 的最优解。 证明由模型( n c e p ) 的约束条件知c k w k 且 ，= i j = l + k = 1 ，2 ，刀，故 m - im w k 水= m a x c k ，乃) w k ，k = 1 ，2 ，甩，所以w k 木一q w k c k ，又因为z ( x ) 为关于x 1 = 1j = i + l 的线性增函数，因此z ( 宰一c k ) z ( 比一c k ) ，同时由x k t o ，1 ) ，k = l ，n ；t = 1 ，t 以及 = l ，k = 1 ，刀的约束条件知了， 1 ，丁) ，s ，z ( 心一q ) 瓯= 彳( 一q ) 以，因此 t = l 7 1 z ( 幸一唧k 宰 t = l = m i n f t ( w + 一龟) l f = 1 ，丁) 以 m i n f , ( w t - c t ) t = 1 ，丁 巩 彳( 比一c k ) 喀 7 z ( 一q h 靠 1 0 疗 ，2， l = 后m 吒+ 办时，该三角运算就用吃+ 叱替换九，从而在l 和屹 之间寻找更短的路径，如图2 1 ， 1 ， 图2 1 三角运算 引理2 1 对相继值= 1 ，2 ，2 进行三角运算，则每一个以都变为从v 到咋的s 卯 的长度。 证明见参考文献 3 3 。 基于三角运算，f l o y d w a r s h a l l 算法的过程如下： i n p u t 】； 地q 一 心 ，lz r硝。蹦 办+ 办+ 吆时，用吃+ 办+ 叱替换农，如图 ( 力) 图2 4 新的三角运算 定理2 3 对相继值j = 1 ，2 ，n 进行三角运算，则每一个以都变为从v 到攻的 n s t p 的长度。 1 6 第一二章网络容鼙按需扩张模型 证明 用归纳法，当v ，v k 外只有一个顶点u ，即j = 1 时，a r k = m i n d ，k ，4 - + 破+ 4 i ) ， 结论显然成立。假设当，唯外有刀一1 个顶点，即j = l ，2 ，n - 1 时结论成立，则当v ，k 外 有刀个顶点，即= 1 ，2 ，刀时，对任意矗 1 ，2 ，刀) ，由前面的假设知叱，叱。均已达 到最短路，取 如l 矗= m i n d ，k ，叱+ 九+ 叱t ) ， d k = m i n d ，ki ，五= 1 ，2 ，门) ， 则a r k 转化为v iv k 之间最短路的长度，结论成立。 从而得到新的f l o y d w a r s h a l l 算法的扩展算法( f l o y d - w a r s h a l l e x p a n d i n g a l g o r i t h m ) ，记为f w e 算法，如下： i n p u t 吒 ， 办) ： f o ri = 1 ，n ，d o z ，：= o o ： f o rj = 1 ，珂，d o f o ri = i ，n ，i ，d o f o rk = 1 ，i ，k j ，d o d k m i n 4 女，dq + 咖j + d 心 e n d 此时，初始值为0 的矩阵 彘 也发生变化： 和髋鬻妒”叱。 模型( n c e p ) 的算法也发生一点改动，生成新的算法： 算法2 2 ( 1 ) 利用f w e 算法求出所有节点对之间的最短路岛，i = 1 ，m - 1 ，j = 2 ，m 及 其所包含的边； ( 2 ) 一( 1 0 )