最短路问题的Bellman-Ford算法(2)

1、第第1页页最短路问题求解方法最短路问题求解方法 Dijkstra算法算法 逐步逼近算法逐步逼近算法 路矩阵算法路矩阵算法第第2页页最短路问题求解方法最短路问题求解方法 Dijkstra算法算法(荷兰荷兰:标号法标号法) 逐步逼近算法逐步逼近算法(Ford(Ford(美国美国) )算法算法):):修正标号法修正标号法 路矩阵算法路矩阵算法(Floyd(Floyd(佛洛伊德佛洛伊德) )算法算法)第第3页页逐次逼近算法思想逐次逼近算法思想 )1(11)(1ijkinikjwPMinP该公式表明，该公式表明， P(1)1j中的第中的第j个分量等于个分量等于P(0)1j的分量与基的分量与基本表本表(权

2、矩阵权矩阵)中的第中的第j列相应元素路长的最小值，列相应元素路长的最小值，它相当它相当于在于在v1与与vj之间插入一个转接点之间插入一个转接点(v1,v2,vn中的任一个，中的任一个，含点含点v1与与vj)后所有可能路中的最短路的路长；每迭代一后所有可能路中的最短路的路长；每迭代一次，就相当与增加一个转接点，而次，就相当与增加一个转接点，而P(k)1j中的每一个分量中的每一个分量则随着则随着k的增加而呈不增的趋势！的增加而呈不增的趋势！v1v2v312-3( )(1)11kkjjPP(0)11jjPw第第4页页用于计算带有用于计算带有负权弧负权弧指定点指定点v1 1到其余各点到其余各点的最短路

3、的最短路)1(11)(1ijkinikjwPMinPj=1,2,n. k=1,2,tn.2.2.计算计算逐次逼近算法基本步骤逐次逼近算法基本步骤(0)11jjPw j=1,2,n.1.1.令令(k)(1)11kjjPP其元素即是其元素即是v1 1到到vj j的最短路长。的最短路长。3.3.当出现当出现时，时，v1v2v312-3例例 计算从计算从点点v1 1到所有其它顶点的最短路到所有其它顶点的最短路解：初始条件为解：初始条件为 0000111213140,2,5,3PPPP 以后按照公式以后按照公式 进行迭代。进行迭代。 直到得到直到得到 ，迭代停止。，迭代停止。v1v2v3v4v6v5v8

4、v72-35467-24-3342-1)1(11)(1ijkinikjwPMinP) 1(1)(1tjtjPP(0)11jjPwv1v2v3v4v5v6v7v8v8v7v6v5v4v3v2v1wij 01jP 11jP 21jP 31jP 41jP 51jPv1v2v3v4v6v5v8v72-35467-24-3342-1400-160240-33-3075-20420002530212303125613611021230312561236613681502123031236531236612366136871412368100212303123653123661236879123681002

5、123031236612368791236810123653利用利用下标下标追踪追踪路径路径)1(11)(1ijkinikjwPMinP基本表基本表空格为无穷大空格为无穷大P1j表示从第一个顶点v1到其余各个顶点的最短路,(0)表示迭代次数,表示最多经过中转的次数第第7页页v1v2v3v4v5v6v7v8v8v7v6v5v4v3v2v1wij 01jP 11jP 21jP 31jP 41jP 51jPv1v2v3v4v6v5v8v72-35467-24-3342-1400-160240-33-3075-2042000253021230312561361102123031256123661368

6、1502123031236531236612366136871412368100212303123653123661236879123681002123031236612368791236810123653利用利用下标下标追踪追踪路径路径)1(11)(1ijkinikjwPMinP基本表基本表空格为无穷大空格为无穷大第第8页页最短路问题求解方法最短路问题求解方法 Dijkstra算法算法 逐步逼近算法逐步逼近算法 路矩阵算法路矩阵算法第第9页页最短路问题求解方法最短路问题求解方法 Dijkstra算法算法 逐步逼近算法逐步逼近算法 路矩阵算法路矩阵算法第第10页页 某些问题需要求网络上某些问题

7、需要求网络上任意两点任意两点间的最间的最短路。当然，它也可以用标号算法依次改变短路。当然，它也可以用标号算法依次改变始点的办法来计算，但是比较麻烦。始点的办法来计算，但是比较麻烦。 这里介绍这里介绍FloydFloyd在在19621962年提出的年提出的路矩阵法路矩阵法，它可直接求出网络中它可直接求出网络中任意两点间的最短路。任意两点间的最短路。FloydFloyd算法算法( (路矩阵法路矩阵法) )思想思想第第11页页 考虑考虑D D中任意两点中任意两点vi i，vj j，如将，如将D D中中vi i，vj j以外的点都删掉，以外的点都删掉，得只剩得只剩vi i，vj j的一个子网络的一个子

8、网络D D0 0，记，记ij(0)ij ,A ijwv vd当否wijij为弧（为弧（ vi i，vj）的权。）的权。 在在D D0 0中加入中加入v1 1及及D D中与中与vi i，vj j，v1 1相关联的弧，相关联的弧，得得D D1 1，D D1 1中中vi i到到vj j的最短路记为的最短路记为 , ,则一定有则一定有(1)ijd(1)(0)(0)(0)i11j min, ijijddddvivjv1wijFloydFloyd算法算法( (路矩阵法路矩阵法) )思想思想 网络网络D=D=（V V，A A，W W），令），令U=(U=(d dijij) )n n n n， 表示表示D D

9、中中vi i到到vj j的最的最短路的长度。短路的长度。dij第第12页页 再在再在D D1 1中加入中加入v2 2及及D D中与中与vi，vj，v1， v2相关联的弧，得相关联的弧，得D D2 2，D D2 2中中vi到到vj的最短路长记为的最短路长记为 ，则有，则有(2)ijd(2)(1)(1)(1)iji22 j min, ijddddFloydFloyd算法算法( (路矩阵法路矩阵法) )思想思想(1)(0)(0)(0)i11j min, ijijdddd第第13页页FloydFloyd算法算法( (路矩阵法路矩阵法) )步骤步骤设有有向网络设有有向网络D=D=（V V，A A），其权

10、矩阵为），其权矩阵为A=(A=(aijij) )n nn n，AvvjiAvvwajijiijij),( , 0),( ,如下构造如下构造路矩阵序列路矩阵序列：则则n n阶路矩阵阶路矩阵D D( (n)n)中的元素中的元素d d(n)(n)ijij就是就是vi i到到vj j的最短路的路长。的最短路的路长。 令权矩阵令权矩阵A A为初始路矩阵为初始路矩阵D D（0 0），），即令即令D D（0 0）=A=A2. 2. 依次计算依次计算K K阶路矩阵阶路矩阵D D（K K）= =（d(k)(k)ijij）n nn n, k=1,2, k=1,2, ,n n，,) 1() 1() 1()(kkjk

11、ikkijkijdddMind这里这里第第14页页路矩阵序列的含义路矩阵序列的含义 K K阶路矩阵阶路矩阵D D（K K） 其中的元素表示相应两点间可能以点其中的元素表示相应两点间可能以点v1、v2、vk为为 转接点的所有路中路长最短的路的路长。转接点的所有路中路长最短的路的路长。 D（0） 其其中的任一元素表示相应两点间无转接点时最短路路长。中的任一元素表示相应两点间无转接点时最短路路长。一阶路矩阵一阶路矩阵D D（1 1） 其中的其中的元素表示相应两点间可能以点元素表示相应两点间可能以点v v1 1为转接点的所有为转接点的所有路中路长最短的路的路长；路中路长最短的路的路长；为使计算程序化，

12、转接点按为使计算程序化，转接点按顶点下标的顺序顶点下标的顺序依次加入依次加入n n阶路矩阵阶路矩阵D D( (n)n) 其中的元素其中的元素d d(n)(n)ijij就是就是vi到到vj的可能以点的可能以点v1、v2、vn为为转接点的所有路中路长最短的路的路长。既是转接点的所有路中路长最短的路的路长。既是vi到到vj的最的最短路的路长。短路的路长。第第15页页例例 求如下交通网络中求如下交通网络中各对点间最短路路长各对点间最短路路长。051250 102 A2302826042440该图的权矩阵为该图的权矩阵为：FloydFloyd算法算法( (路矩阵法路矩阵法) )算例算例31025v4v1

13、v2v5v312262448第第16页页例例 求如下交通网络中求如下交通网络中各对点间最短路路长各对点间最短路路长。FloydFloyd算法算法( (路矩阵法路矩阵法) )算例算例 0051250 102 D =A230282604244031025v4v1v2v5v312262448 0051250 102 D =A2302826042440(1)(0)(0)(0)i11j min, ijijdddd利用公式利用公式发现发现第一行，第一列元素不变第一行，第一列元素不变 105125 D220213621472302841274133042440031025v4v1v2v5v312262448

14、 105125 D2202136214723028412741330424400(2)(1)(1)(1)i22j min, ijijdddd利用公式利用公式发现发现第二行，第二列元素不变第二行，第二列元素不变 255 D02136234127221472147023255413344400121257202521731025v4v1v2v5v312262448 255 D0213621472302325541274133042440012214712572025217(3)(2)(2)(2)i33j min, ijijdddd利用公式利用公式发现发现第三行，第三列元素不变第三行，第三列元素不变

15、 3 D2136323255413341200132421325652147224132604531624031025v4v1v2v5v312262448002147204127042400221471257 3 D213632325541334120013242132565021472241326045316240 4 D0213623032552011325/1456202413264133440221472531/5416413245(4)(3)(3)(3)i44j min, ijijdddd利用公式利用公式发现发现第四行，第四列元素不变第四行，第四列元素不变31025v4v1v2v5v

16、31226244831025v4v1v2v5v312262448 4 D021362147230325502401202413264133440221472531/54164132451325/1456D(5)中的元素给出相应两点间中的元素给出相应两点间的最短路，其下标给出最短路的最短路，其下标给出最短路个顶点下标个顶点下标,比如：比如： 5 D021362147230325502401202413264133440221472531/54164132451325/14566254第第22页页已知有已知有7 7个村子，相互间道路的距离如下图示。拟合建一所个村子，相互间道路的距离如下图示。拟合建

17、一所小学，已知小学，已知A A处有小学生处有小学生3030人，人，B B处处4040人，人，C C处处2525人，人，D D处处2020人，人，E E处处5050人，人，F F处处6060人，人， G处处60人人,问小学应建在哪一个村子，问小学应建在哪一个村子，使学生上学最方便（使学生上学最方便（原则所有人走的总路程最短；尽可原则所有人走的总路程最短；尽可能公平。）。能公平。）。最短路问题算例最短路问题算例1(1(选址问题选址问题) )AGFECB522747163D26第第23页页 0052502 72074 D270 6 276 0 1 342 1 0 63 6 0A 最短路问题算例最短路

18、问题算例1(1(选址问题选址问题) )AGFECB522747163D26第第24页页 21331210525072 72 7074 D270 6 276 0 1 342 1 0 63 6 0 最短路问题算例最短路问题算例1(1(选址问题选址问题) ) 0052502 72074 D270 6 276 0 1 342 1 0 63 6 0A 12412521331220527125072 72 7074 D270 6 276 0 1 342 1 0 63 6 0 21331210525072 72 7074 D270 6 276 0 1 342 1 0 63 6 0 1241251362132

19、13631213253421521521363163205271265072 7 112707 144 D7270 6 2127146 0 1 361142 1 0 63 6 0 12412521331220527125072 72 7074 D270 6 276 0 1 342 1 0 63 6 0 12412513621324631213254421521521363163205271265072 7 42707 144 D7270 6 2127146 0 1 36442 1 0 63 6 0 124125136213213631213253421521521363163205271265

20、072 7 112707 144 D7270 6 2127146 0 1 361142 1 0 63 6 0 12412513612547213246257312132513257542145752152136316326577521752752137547560527126155072 7 4102707 144 17 D727026912714610364420141510179430 12412513621324631213254421521521363163205271265072 7 42707 144 D7270 6 2127146 0 1 36442 1 0 63 6 0 124

21、13651361365721324652462465731236436536576421463465465756315462563564631632657756317564275637564756052776105072 548270654 8 D72602367553103644201410886430 12412513612547213246257312132513257542145752152136316326577521752752137547560527126155072 7 4102707 144 17 D727026912714610364420141510179430 1241

22、3651361365721324652462465731236436536576421463465465756315462563564631632657756317564275637564756052776105072 548270654 8 D72602367553103644201410886430 12413651361365721324652462465731236436536577421463465465756315462563564631632657756317564275637564756052776105072 548270654 8 D72602367553103644201

23、410886430 12413651361365721324652462465731236436536577421463465465756315462563564631632657756317564275637564756052776105072 548270654 8 D72602367553103644201410886430A A处处3030人，人，B B处处4040人，人，C C处处2525人，人，D D处处2020人，人，E E处处5050人，人，F F处处6060人，人， G G处处6060人人. .02005014035036060015001754025024048060280

24、0120250240480210801500150120360210200125600601801801601004050024030032020012025024001700 1335 1430 1070 835 1330A B C D E F GABCDEFG第第32页页某工厂使用一台设备，每年年初工厂都要作出决定：如果继某工厂使用一台设备，每年年初工厂都要作出决定：如果继续使用旧的，要付维修费；如果买新的，要付购置费。试制续使用旧的，要付维修费；如果买新的，要付购置费。试制定一个五年更新计划，使工厂总支出最少？定一个五年更新计划，使工厂总支出最少？若该设备在各年的购置费、不同役龄的残值及

25、维修费如下表：若该设备在各年的购置费、不同役龄的残值及维修费如下表：项目项目购置费购置费设备役龄设备役龄维修费维修费残值残值第一年第一年 第二年第二年 第三年第三年第四年第四年 第五年第五年 11 0- -1 5 4 12 1- -2 6 3 13 2- -3 8 2 14 3- -4 11 1 15 4- -5 18 0 最短路问题算例最短路问题算例2(2(设备更新问题设备更新问题) )第第33页页最短路问题算例最短路问题算例2(2(设备更新问题设备更新问题) )项目项目购置费购置费设备役龄设备役龄维修费维修费残值残值第一年第一年 第二年第二年 第三年第三年第四年第四年 第五年第五年 11 0- -1 5 4