最短路的灵敏度分析

最短路的灵敏度分析 第22卷第2期 2002年6月 数学理论与应用 MATHEMATICALTHEORYANDAPPLICATIONS V0I.22No.2 Jone2002 最短路的灵敏度分析' 陈挚谢政 (国防科技大学兵学院,长沙,410072) 摘要最短路的灵敏度分析就是讨论当网络中边的权值发生波动时,对目前的最短 本文讨 路带来的影响. 论了网络中边的权值在何种范围内变化时,极小最短路子网络不发生变化. 关键词最短路极小最短路子网络灵敏度分析 TheSensitivityAnalysisoftheShortestPath ChenZhiXieZheng (DeartmentofMathematics,NUDT,Changsha,410072) AbstractThesensitivityanalysisoftheshortestpathdiscusswhatistheeffecttOthenowshorte stpath. whentheedgeweightsinthenetworkchange.Inthisthesis,whichrangetheedgeweightsinthe network changewouldbediscussed.whenpindingtheshortestpathsubnetworkdonotchange. Keywordstheshortestpathpindingtheshortestpathsubnetworksensitivityanalysis. 在以前讨论最短路问时,都假定网络中各边的权值是常数,但是实际上这些常数 往往是 估计值或预测值.因此,提出这样一个问题,即当网络中的弧的权值在什么范围内 发生变化时, 极小最短路子网络不发生变化. 显然,在网络中的某些弧的权值发生变化后.原来的极小最短路子网络一般不会发生变 化.当然,我们可以用Dijkstra算法重新计算得到新的极小最短路子网络.不过这样太麻烦,因 为在很多情况下,极小最短路网络是不发生变化的.灵敏度分析就是讨论网络中各条弧的权值 在何种范围内变化时极小最短路子网络不发生变化.下面对极小最短路子网络中弧的权值变 化进行讨论. 极小最短路子网络中弧(,,,)的权值发生变化可以是权值勤变小,也可以是权值变大, 我们分别讨论其上限和下限.在此之前,先给出一个引理. 引理在图D一(,A,?/)的极小最短路子网络H中,任给一弧(,,),如果有_一点, 使得(,,)不在从t,到的所有路中,则弧(t,)的权值不能发生变化,否则极小最短路子 网络发生变化. 证明设(,,)不在从到所有的路中,如果存在一条从,到的路尸含(.,), 也存在一条路尸z不含(,,),由于都是从t,到的最短路.因此(尸)一w(尸),它们都是 ? 刘德铭教授推荐 收稿日期:2001年8月6日 第2期最短路的灵敏度分析1O5 .到的最短路的长.此时,若(,,)的权值变小,则W(P)<W(P),尸就不是到的 最短路,极小最短路子网络发生变化:如果,)的权值变大,则W(尸)<W(尸),此时尸就 不再是到的最短路,极小最短路子网络也发生了变化.因此,要使极小最短路子网络不发 生变化,(,"Ui)的权值就不能发生变化. 定理1【1设网络D一(,a,)不含负回路,则对一切.,?V,最短路(,)的任何 (p,)节是D中最短(,"Uq)路. 设图H一(,A,)为图D=(,A,)的极小最短路子网络,弧(,)为图H的一 条割边.支掉弧(t,,)后,项点集分为两个部分和\,其中?V,?V\,,由 导出的子图记为H一H[\]和由\导出的子图记为H一H[\],则H与H之 间不连通.因此当弧(,)权值勤发生变化时,由定理1易得: 定理2当,变小时,经过弧(,)的最短路无任何影响,因而\中各点的最短路 不变,当.,变大时,不经过弧(,"Uj)的最短路无任何影响,因此中各点的最小路不变. 根据上面的引理可得,在求弧的权值的变化范围时,应先判断是不是割边.如果不是割边, 则该弧不能发生变化;如果是割边,由定理2可知,当该弧的权值发生变化时,网络中只有一部 分点的最短路受到影响.由此我们给出为保证极小最短路子网络不发生变化,求极小最短路子 网络中弧(,"Ui)的权值变化范围的具体算法; 设在图D一(,A,)中用文献[2]中的Dijkstra算法可求出J[)的极小最短路子网络记 (,A,).对于e=VV奄A,,?V(J[)),我们规定W一+cx3.其中为的 为H一 前点坐标,g为的后点坐标. Step0在图H中,去掉弧(,)得到的图记为H一(,A,),并令R一{Ig,一 }/一厂J\{},g一g.\{},v一{},S一v,转step1. Step1若?V,则停止,H连通,(,,)不是割边,()不能发生变化;否则V与 \之间有弧,转step2;如果与v\v之间没有弧,不连通,(,"Uj)是割边,转step3. Step2令S=V,计算 V一{I?g,?S}US2U{I?',,?S} 置S1一Vl2,转step1. Step3在图D中,V?V\,计算 7'(^)一min{"^+W,",?Vl} 71,(^)一min{"^+W,女__"I?V1} 转step4. Step4置 ?1W=min{7'()It?v\v1} ?w,一min{7()It,^?V\1} 转step5 Step5弧(,)的权值变小时满足 i?0当W,一A1W<0时 >训._.A.当Wf!一?砌<O时(1) 弧(,)的权值变大时满足 1O6效学理论与应用第22卷 :J<W,J+A2wq(2) 证明要不变化,就要保证既不增加弧,也不减少弧.由定理2可知,当wii变小时, ,中各点最短路不发生变化,所以我们只需讨论中各点最短路是否发生变化.丁()可 以保证以,中点为起点指向,中点的弧不会进来,当W满足公式(1)时,从\,中点 指向,中点的弧都不会进来.同时,极小最短路子网络中的弧也不会出去.事实上,设a一 (,,)为极小最短路子网络中的一条弧.若a位于由导出的子图中,因为,的最短路不 变,所以a仍为新的极小最短路子网络中的弧.而a若位于由导出的子图中,由于\,以中 点为起点指向,中点的弧不能进来,因此新的,最短路不包含(,),,的最短路不发生 变化,a仍然在,的某一条最短路中.此时,中各点的最短路也就不会发生变化.综上可知, 当w,满足(1)时,极小最短路子网络不会发生改变.另一方面,若W变小到不满足(1)时,由 公式T(v)可知肯定有从中点指向,中点的弧进入到极小最短路子,来,也就是说,, 中某点的最短路会发生变化,极小最短路子网络也就发生了变化.故W,必须满足(1). 当W变大时,同样由定理2知,中各点的最短路不发生变化,我们只需讨论,中各 眯的最短路是否会发生变化.而7()可以保证以中点为起点指向.中点的弧不会 进来,所以,当W,满足(2)时,从,中点指点向,中点的弧都有不会进来,同时,极小最短 路子网络中的弧也不会出去.事实上,设a一(,,)为极小最短路子网络中的一条弧,若a位 于由,导出的子图中,因为,的最短路不变,所以a仍为新的极小最短路子网络中的弧.而a 位于由,导出的子图中,由于以,中点为起点指向,中点的弧都有不进来,因此,新的 的最短路一定包含(,),的最短路也不发生变化,a仍然在的某一条最短路中,此时 \的1中各点的最短路也就不会发生变化.综上可知,当W满足(2)时,极小最短路子网络 不会发生改变.此时,中点的最短路不发生变化.所以说,当W,满足(2)时,极小最短路子 网络不会改变.另一方面,若W,变大到超出了(2)给出的范围时,由公式7()可知有.中 点的最短路会发生变化.必须满足(2). 综上可得,极小最短路子网络中弧权值的变化范围由(1)和(2)给定. 定理3求最小最短路子网络中弧(,),的权值勤的变化范围的算法复杂性为O(). 证明在上面的算法中,step0只需进行2次减法和次判断,Step1,Step2至多循环 次,在第r次循环中,至我要进行一r次判断,所以总共要进行(一1)/2次判断;Step3要 进行(一1)/2次加法和减法,以及(一1)/2次比较;Step4只需进行次比较;Step5只需 进行1次判断,因此,算法总的复杂性为0(2++,z(一1)/2+(一1)++1)一o(). 参考文献 [1]谢政,李建平.网络算法与复杂性理论.长沙:国防科技大学出版社.1995 [2]J.A.BondyandU.S.R.Murty.G.raphtheorywithApplications.TheMacmillamPressLtD ,1976 [3]田丰,马仲蕃.图与网络流理论.北京:科学出版社,1987