d图论例子(存档)(北邮信通院陈鑫林教授授课PPT)

1、1 若干补充若干补充1.1.Ford(1956)-Moore(1957)-Bellman(1958)Ford(1956)-Moore(1957)-Bellman(1958) 算法算法由于由于DijkstraDijkstra算法只适用于弧长为正的情形算法只适用于弧长为正的情形, ,而而Ford(1956)-Moore(1957)-Bellman(1958)Ford(1956)-Moore(1957)-Bellman(1958)算法适算法适用于弧长可为负用于弧长可为负, ,但不含负的有向回路的情形但不含负的有向回路的情形, ,并且并且在许多通信的论文中得到广泛应用在许多通信的论文中得到广泛应用,

2、,所以特做介绍所以特做介绍. .2Ford(1956)-Moore(1957)-Bellman(1958)Ford(1956)-Moore(1957)-Bellman(1958)算法算法它适用于弧长可为负它适用于弧长可为负, ,但不含负的有向回路的情形但不含负的有向回路的情形. .算法思路算法思路: :从从s s到到j j至多至多k+1k+1条弧的最短有向路径可以条弧的最短有向路径可以由从由从s s到到j j至多含至多含k k条弧的最短路径得到条弧的最短路径得到. .因此因此, ,在第在第k k次迭代结束时次迭代结束时, ,节点的标记就表示从节点的标记就表示从s s出发的含不多出发的含不多于于

3、k+1k+1条弧的最短路径的长度条弧的最短路径的长度. .设设 是给定的有是给定的有n n个节点的网络个节点的网络G(V,E,l)G(V,E,l)中从中从s s到到j j的不多于的不多于k k条弧的最短有向路径的长度条弧的最短有向路径的长度, ,首先设首先设)(kjl1, 2 , 1),(, 0)1()(njjslllljkss1, 2 , 1,),(min,min,),()()()1(njsjijillllEjikikjkj对所有对所有3显然显然, ,从从s s到到j j至多含至多含k+1k+1条弧的最短有向路径条弧的最短有向路径可能由可能由k+1k+1条弧或较少的弧构成条弧或较少的弧构成,

4、 ,若它正好含若它正好含k+1k+1条条弧弧, ,则设则设(i,j)(i,j)是是 中的最后一条弧中的最后一条弧, ,那么那么 可以可以看成是由从看成是由从s s到到i i的含的含k k条弧的最短路径条弧的最短路径 和后续弧和后续弧(i,j)(i,j)构成构成, ,因此得因此得 的长度是的长度是如果如果 含含k k条或较少的弧条或较少的弧, ,则则 . .因此对因此对kn, kn, 时时, ,算法终止算法终止. .如果在如果在k=n-1k=n-1时时对某个对某个j j有有 , ,那么网中必有负向回路那么网中必有负向回路, ,算法失算法失效效, ,并在第并在第n-1n-1次迭代时终止次迭代时终止

5、. .表明有负向回路表明有负向回路. .算法的计算复杂度为算法的计算复杂度为)1(,kjsP)1(,kjsP)1(,kjsP)1(,kjsP),(min)()()1(,)1(jillPllkikjskj)1(,kjsP)()1(kjkjll)()1(kjkjll)(3nO)()1(kjkjll)(,kisP4例例6664444811223555S570Sl4,44,4)1(1)2(1)3(1)4(1llll)1(4)2(4)3(4)4(4,95,5llll6,66,6)1(2)2(2)3(2)4(2llll)1(5)2(5)3(5)4(5,00,0llll40)3(6)4(6ll133)3(3

6、)4(3ll)1(3)2(313ll)1(6)2(6ll5,)6,5(),6,4(,min)2,00,min)5 ,3(),5 ,2(,min)1,99 ,min)4,5(),4, 1(,min)2,13876min,min)3 ,4(),3 ,2(min,min)2,( ,6min,4)2, 16min(,4min)1 ,3(),1 ,2(min,min)1(6,5 ,4,3,6,4:)1(5)1(4)1(6)2(6)1(3)1(2)1(5)2(5)1(5)1(1)1(4)2(4)1(4)1(2)1(3)2(3)1(2)1(2)2(2)1(3)1(2)1(1)2(1)1()1(2)1(1ll

7、llllllllllllllllllllllslllllllllkillli（经经（经经（经经，的的径径无无其其它它到到外外除除第第一一次次迭迭代代初初始始6)5( ,440,59min,min)6,5(),6,4(,min,0413,66min,0min)5,3(),5,2(,min)5( ,550,54min,9min)4,5(),4, 1(,min,1389,76min,13min)3,4(),3,2(min,min,6min4)213, 16min(,4min)1 ,3(),1 ,2(min,min)2()2(5)2(4)2(6)3(6)2(3)2(2)2(5)3(5)2(5)2(1)

8、2(4)3(4)2(4)2(2)2(3)3(3)2(2)2(2)3(2)2(3)2(2)2(1)3(1经经再再经经第第二二次次迭迭代代lllllllllllllllllllllllllllllllllk7)4( ,040,55min,4min)6,5(),6,4(,min,0413,66min,0min)5,3(),5,2(,min,550,54min,5min)4,5(),4, 1(,min)4( ,385,76min,13min)3,4(),3,2(min,min,6min,4)1 ,3(),1 ,2(min,min)3()3(5)3(4)3(6)4(6)3(3)3(2)3(5)4(5)3

9、(5)3(1)3(4)4(4)3(4)3(2)3(3)4(3)3(2)3(2)4(2)3(3)3(2)3(1)4(1再再经经再再经经第第三三次次迭迭代代lllllllllllllllllllllllllllllllllk8,),(min,min)4()4()4()4()5(jiijjljillllk第第四四次次迭迭代代算法在k=4n=7次迭代终止.0)(),6 ,4(),4, 5(),5 ,2(),2,()6 ,4( ,:6, 3)(),3 ,4(),4, 5(),5 ,2(),2,()3 ,4( ,:3, 5)(),4, 5(),5 ,2(),2,()4, 5( ,:4,0)(),5 ,2(

10、),2,(:5,6)(),2,(:2,4)(),1 ,(:1)4(6,)3(4,)4(6,)4(3,)3(4,)4(3,)3(4,)2(5,)3(4,)2(5,)2(5,)1(2,)1(2,)1(1 ,)1(1 ,sssssssssssssssPlsPPsPlsPPsPlsPPsPlsPsPlsPsPlsPs92.Floyd2.Floyd算法在以下情况可以简化算法在以下情况可以简化: :(1)(1)如有度数为如有度数为1 1的端的端, ,可把它们去掉再做计算可把它们去掉再做计算; ;设设 为度数为为度数为1 1的端的端, ,它只与它只与 相连相连, ,则则 与其它与其它端的最短径必经端的最短径

11、必经 , ,所以所以(2)(2)如有度数为如有度数为2 2的端的端, ,则按下述方法去掉则按下述方法去掉: :设设 为度数为为度数为2 2的端的端, ,它只与它只与 相连相连, ,若若 , ,则可简单地去掉则可简单地去掉若若 , ,也可去掉也可去掉 , ,但把但把 改成改成 svivsviv)(表表最最短短距距离离wwdwijsisjsvjivv 和和ijsisjdddsvijsisjdddsvijd;sisjdd10不论那种情况不论那种情况, ,与其它端间的最短径长用下述公式与其它端间的最短径长用下述公式计算计算: :(3)(3)稀疏网的情况下可把全图分成几个部分来计算稀疏网的情况下可把全图

12、分成几个部分来计算, ,然后合并然后合并. .当网的边数远少于全联网的边数时当网的边数远少于全联网的边数时, ,称称稀疏网稀疏网. .此时往往存在割端或端数较少的割端此时往往存在割端或端数较少的割端. .对于有割端对于有割端 的网的网G,G,去掉后就把去掉后就把G G分成几部分分成几部分( (例例如三部分如三部分G1,G2,G3),G1,G2,G3),用用FloydFloyd算法分别求出算法分别求出的最短距离阵的最短距离阵 及路由阵及路由阵. .若若则则 间最短距离为间最短距离为,jksjiksiskwdwdMinwsv,321sssvGvGvG ,WWW221,GvGvijivv , jsi

13、sijwww111v22v3v4v5v6v7v8v1213345689019105350293208046840212036130)0(D例例1201641612141310531511131265021410121143201281091615141204651211108402114131210620313121195130)1(D0077777700005555700055557000303375530033755000007553300075533000)1(R,13875313153175187118vvvvvvvvvvvvvvvvw131v22v3v4v5v6v7v8v121334

14、5689. 4 , 3 , 2 , 1, 80033000030003000,0465402162035130353535) 1 () 1 (idwwdRDii14030333003300000330003300001281091204658402110620395130) 1 () 1 (RD151v22v3v4v5v6v7v8v1213345689. 8 , 7 , 6 , 5; 4 , 3 , 2 , 1, 80077000070007000,0164105365024320535335) 1 () 1 (ijjijiijwwjiddwwdRD16(3)(3)次短径和可用径次短径和可用径

15、: :若两端间有几条径若两端间有几条径, ,其中其中P1P1为最短径为最短径, ,而而P2P2与与P1P1无无公共边却有公共端公共边却有公共端, ,则称则称P2P2不共边径或边分离径不共边径或边分离径; ;若若P3P3与与P1P1除起终点外无公共端除起终点外无公共端( (必无公共边必无公共边),),则称则称P3P3为不共端径或端分离径为不共端径或端分离径. .求次短径的方法求次短径的方法1)1)对不共边径对不共边径从图中去掉最短径的所有边从图中去掉最短径的所有边, ,然后在剩下的图中求然后在剩下的图中求最短径最短径; ;2)2)对不共端径对不共端径从图中去掉最短径的所有中间端从图中去掉最短径的

16、所有中间端( (当然段的关联边当然段的关联边也去掉也去掉),),然后在剩下的图中求最短径然后在剩下的图中求最短径; ;17这个过程还可继续下去.例:1v2v3v4v5v6vsvtv11111222335618从从 到到 有三条径有三条径: :svtv)(:)(:)(:6534232211端分离径端分离径边分离径边分离径最短径最短径tststsvvvvPvvvvvPvvvvP191v2v3v4v5v6vsvtv111223356边分离的次短径203v4v5v6vsvtv112235端分离的次短径21可用径可用径在某些应用中在某些应用中,要求找一批满足条件的径要求找一批满足条件的径.当有几个当有几

17、个条件时条件时,可先用一个条件求可用径可先用一个条件求可用径,再在其中筛选出再在其中筛选出满足其它条件的可用径满足其它条件的可用径.今用限制条件为径长的例子来说明算法今用限制条件为径长的例子来说明算法:仍用上图仍用上图,要求径的长度小于要求径的长度小于M(=7)的可用径的可用径.1)用用F算法求出图的最短径长矩阵算法求出图的最短径长矩阵W和转接矩阵和转接矩阵R;2)若若 ,则无可用径则无可用径, 若若 ,则找一个则找一个 的邻接节点的邻接节点 ,如果如果 则排除则排除,否则就得一可用径否则就得一可用径MwstMwstsvivMwditsiitPis),(22本例的距离矩阵本例的距离矩阵, ,最

18、短路径和转接矩阵分别如下最短路径和转接矩阵分别如下011110550210103211302620122610D230030303300088888300312100830303338130010882000023813100038030200,0161413410525245650645321260413445440332125130233433320145242310RS)( , 862, 642)( , 716, 43155332211tstststswdwdwdwd是可用径.再看V1与V3能否延续ttPsPs31) 3 ,( ,) 1 ,(24与与V1V1相连的有相连的有V2,V2,与

19、与V3V3相连的有相连的有V2.V2.)( , 711132, 611121, 6132, 4121424323421424121232323212121tststststststswdddvvvvvwdddvvvvwddvvvvwdd与与V2V2相连的有相连的有V4.V4.)( , 71132, 51121424323421424121tststswdddvvvvvwddd251v2v3v4v5v6vsvtv11111222335626(4)(4)图的中心和中点图的中心和中点从端间最短距离出发可定义网的从端间最短距离出发可定义网的中心中心, ,中点中点和和直径直径一个端一个端 在网内的位置可用最长的最短径表示在网内的位置可用最长的最短径表示: : 的最小值所对应的端定义为网的中心的最小值所对应的端定义为网的中心: :网的网的中点中点可定义为平均最短径长最小的端可定义为平均最短径长最小的端: :ijjiwMaxt ivit*iiitMint ,*iiijijisMinsws27网的直径网的直径: :例例1