大二下運(yùn)籌學(xué)

1、 第三節(jié) 最短路問題一、最短路問題的提出例 下圖為單行線交通網(wǎng)，每弧旁的數(shù)字表示通過這條 線所需的費(fèi)用?，F(xiàn)在某人要從v1出發(fā)，通過這個(gè)交 通網(wǎng)到v8去，求使總費(fèi)用最小的旅行路線。v2v523464v3v1v4v6121061210v8v9v72363v2v523464v3v1v4v6121061210v8v9v72363從v1到v8：P1=（v1，v2，v5，v8） 費(fèi)用 6+1+6=13P2=（v1，v3，v4， v6， v7， v8） 費(fèi)用 3+2+10+2+4=21P3= 從v1到v8的旅行路線 從v1到v8的路。旅行路線總費(fèi)用 路上所有弧權(quán)之和最短路問題中，不考慮有向環(huán)、并行弧。最短路

2、問題 給定有向網(wǎng)絡(luò)D=（V，A，W），任意弧aijA，有權(quán)w（ aij ）=wij，給定D中的兩個(gè)頂點(diǎn)vs，vt。設(shè)P是D中從vs到vt的一條路，定義路P的權(quán)（長度）是P中所有弧的權(quán)之和，記為w（P）。最短路問題就是要在所有從vs到vt的路中，求一條路P0 ，使w(P)min)w(PP0 稱P0是從vs到vt的最短路。路P0的權(quán)稱為從vs到vt的最短距離。記為Ust。二、Dijkstra算法 當(dāng)所有 時(shí)，本算法是用來求給定點(diǎn)vs到任一個(gè)點(diǎn)vj最短路的公認(rèn)較好的一種方法。0wij事實(shí)：如果P是D中從vs到vj的最短路，vi是P中的 一個(gè)點(diǎn)，那么，從vs沿P到vi的路是從vs到 vi的最短路。即：

3、最短路的子路也是最短路。（反證法）思想：將D=（V，A，W）中vs到所有其它頂點(diǎn)的最短 路按其路長路長從小到大排列為：u0 u1 u2 unu0表示vs到自身的長度，而相應(yīng)最短路記為：P0，P1，P2，Pn， P1一定只有一條弧。路徑路徑思想：將D=（V，A，W）中vs到所有其它頂點(diǎn)的最短 路按其路長路長從小到大排列為：u0 u1 u2 unu0表示vs到自身的長度，而相應(yīng)最短路記為：P0，P1，P2，Pn， P1一定只有一條弧。 siXv100s0wminu , XVX ,vX0i則記取最小值的點(diǎn)為v1， P1=P（vs，v1）假定 u0，u1，uk的值已求出，對應(yīng)的最短路分別為P1=P（v

4、s，v1）， P2=P（vs，v2）， Pk=P（vs，vk）記kkk21skXVX , v,.,v,v,vX則)v,w(vuminuiiXvXv1kkki使上式達(dá)到最小值的點(diǎn)v 可取為Vk+1。計(jì)算過程中可采用標(biāo)號方法。 XK中的點(diǎn)，ui值是vs到vi的最短路長度，相應(yīng)的點(diǎn)記“永久”標(biāo)號； XK中的點(diǎn)，ui值是vs到vi的最短路長度的上界，相應(yīng)的點(diǎn)記“臨時(shí)”標(biāo)號，供進(jìn)一步計(jì)算使用。前點(diǎn)標(biāo)號 j： 表示點(diǎn)vs到vj的最短路上vj的前一點(diǎn)。如 j=m，表示vs到vj的最短路上vj前一點(diǎn)是vm。Dijkstra算法步驟：第1步：令us= 0，uj=wsj （1jn）若asjA，則令wsj=+ ,

5、X0=vs ，X0=VX0 ，K=0, j=s, (0 jn）第2步：（選永久標(biāo)號）在XK中選一點(diǎn)vi，滿足 jXviuminu Kj 如果ui=+ ，停止，從vs到XK中各點(diǎn)沒有路；否則，轉(zhuǎn)第3步。第3步：（給點(diǎn)vi永久性標(biāo)號） 步轉(zhuǎn)第否則求得到所有點(diǎn)的最短路已經(jīng)結(jié)束如果令4, ; v, ,X ,vXX , vXX s1kik1kik1kv2v523464v3v1v4v6121061210v8v9v72363第4步：（修改臨時(shí)標(biāo)號）令 j=i，uj=ui+wij，否則， j ，uj 不變，把k換成k+1，返回第2步。對所有 如果 , X v1kjjijiuwu 例 用Dijkstra算法求前

6、面例子中從v1到各點(diǎn)的最短路。解：u1=0，u2=6，u3=3，u4=1，u5=u6=u7=u8=u9=+ ，j=1 （j=2，3，9）X0=v1 ，X0=v2，v3，v9 點(diǎn)v4得永久標(biāo)號， 4=1 ，X1=v1，v4， X1=v2，v3， v5，v6 ，v7，v8 ，v9，K=0 minu2，u3，u4，u5，u6，u7，u8，u9 =min6，3，1， =1= u4 在所有vjX1中， u6= ，u4+w46=1+10=11， 即 u4+w46 u6 修改臨時(shí)標(biāo)號u6= 11 ，6=4 ，其余標(biāo)號不變。v2v523464v3v1v4v6121061210v8v9v72363K=0 +1=

7、1 minu2，u3，u5，u6，u7，u8，u9 =min6，3， 11， ， =3= u3 點(diǎn)v3得永久標(biāo)號， 3=1 ，X2=v1，v4 ，v3， X2=v2， v5，v6 ，v7，v8 ，v9， u2= 6 ，u3+w32=3+2=5， 即 u3+w32 u2 修改臨時(shí)標(biāo)號u2= 5 ，2=3 ，其余標(biāo)號不變。在所有vjX2中， 點(diǎn)v2得永久標(biāo)號， 2=3 ， X4=v1，v4 ，v3 ，v2， X4=v5 ，v6 ，v7，v8 ，v9，K=2 +1=3 minu2， u5，u6，u7，u8，u9 =min5， ， 11， ， =5= u2 u6= 11 ，u5+w56=6+4=10，

8、 即 u5+w56 u6 u7= ，u5+w57=6+3=9， 即 u5+w57 u7 u8= ，u5+w58=6+6=12， 即 u5+w58 u8 修改臨時(shí)標(biāo)號u6= 10 ，6=5 ， u7=9 ，7=5 ， u8= 12 ，8=5 ，在所有vjX4中，K=3 +1=4 minu6，u7，u8，u9 =min10，9，12， =9= u7 點(diǎn)v7得永久標(biāo)號， 7=5 ，X2=v1，v4 ，v3 ， v2， v5，v7，X2=v6 ，v8 ，v9，在vjX5中，臨時(shí)標(biāo)號不變。K=4 +1=5 minu6，u8，u9=min10，12， =10= u6 點(diǎn)v6得永久標(biāo)號， 6=5 ，X6=v

9、1，v4 ，v3 ， v2， v5，v7 ，v6，X6=v8 ，v9，點(diǎn)v8，v9臨時(shí)標(biāo)號不變。K=5 +1=6 minu8，u9=min12， =12= u8 點(diǎn)v8得永久標(biāo)號， 8=5 ， 即從v1到v8的最短路長為u8=12， 8=5 ， 5=2 ， 2=3 ， 3=1 ， 知從v1到v8 的最短路為： P1，8=P（v1，v3 ， v2， v5，v8）v2v523464v3v1v4v6121061210v8v9v72363v2v523464v3v1v4v6121061210v8v9v72363(0, 0)(1,6)(1,1)(1,3)(1,)(1,)(1,)(1,)(1,)v2v523

10、464v3v1v4v6121061210v8v9v72363(0, 0)(1,6)(1,1)(1,3)(1,)(1,)(1,)(1,)(4,11)v2v523464v3v1v4v6121061210v8v9v72363(0, 0)(3,5)(1,1)(1,3)(2,6)(5,9)(1,)(5,12)(5,10)v2v523464v3v1v4v6121061210v8v9v72363(0, 0)(3,5)(1,1)(1,3)(2,6)(5,9)(1,)(5,10)(5,12)問題：本例中，v1到v9的最短路？無向網(wǎng)絡(luò)負(fù)權(quán)弧時(shí)。wijvivjwijwijvjvi無向網(wǎng)絡(luò)中，最短路最短鏈。多個(gè)點(diǎn)對之

11、間最短路？v1v2v312-2Dijkstra算法失效三、Floyd算法 網(wǎng)絡(luò)D=（V，A，W），令U=(uij)nn， 表示D中vi到vj的最短路的長度。(n)ij U 考慮D中任意兩點(diǎn)vi，vj，如將D中vi，vj以外的點(diǎn)都刪掉，得只剩vi，vj的一個(gè)子網(wǎng)絡(luò)D0，記否則當(dāng) Av,v wUjiij(0)ijwij為?。?vi，vj）的權(quán)。 在D0中加入v1及D中與vi，vj，v1相關(guān)聯(lián)的弧，得D1，D1中vi到vj的最短路長記為 ，則一定有(1)ijU(0)1j(0)i1(0)ij(1)ij U U,Umin U 如果計(jì)算結(jié)果希望給出具體的最短路的路徑，則構(gòu)造路徑矩陣S=(Sij) nn ,

12、 Sij表示vi到vj的最短路的第一條弧的終點(diǎn)。如 ，則從vi到vj的最短路的第一條弧為（ vi，vt），第二條弧為從vt到vj的最短路的第一條弧。ts (n)ijvivjv1wij 再在D1中加入v2及D中與vi，vj，v1， v2相關(guān)聯(lián)的弧，得D2，D2中vi到vj的最短路長記為 ，則一定有(2)ijU(1)2j(1)i2(1)ij(2)ij U U,Umin U 遞推，D中n個(gè)點(diǎn)逐個(gè)加入子網(wǎng)絡(luò)，終得D中vi到vj的最短路路長 (n)ijijU UFloyd算法步驟：第1步： n)1,2,.,j n;1,2,.,(i j S 其中 , )(SS U U(0)ijnn(0)ij(0)(0)第

13、2步：計(jì)算n)1,2,3,.,(k )S (S n)1,2,3,.,(k ) U( Unn(k)ij(k)nn(k)ij(k)其中1)-(kkj1)-(kik1)-(kij1)-(kik1)-(kkj1)-(kik1)-(kij1)-(kij(k)ij1)-(kkj1)-(kik1)-(kij(k)ijU U U S U U U S S U U,Umin U當(dāng)?shù)?步：當(dāng)k=n時(shí)，的最短路路長到就是元素ji(n)ijnn(n)ij(n)v vU 中 )(U U第一條弧的終點(diǎn)的最短路的到就是元素ji(n)ijnn(n)ij(n)v vS 中 )(SS 例 求如下網(wǎng)絡(luò)中各點(diǎn)對間最短路的路長。v2v5

14、2-344v3v1v4-2658解： 0240842036050 U(0)min ，4+55432154321543215432154321S (0) 用U(0)的第一行、第一列來修正其余的Uij，即作(0)1j(0)i1(0)ij(1)ij U U,Umin U同時(shí)，在修正 處修改(1)ij U(0)i1(1)ijSS 029408942036050 U(1)Min，5+65431154311543215432154321S (1)1SS 1)(k (0)41(1)42同理1S (1)52021594608942036021150 U(2)5411114311543215432124221S (2)2SS 2)(k (1)12(2)13用U1的第二行、第二列修正其余的Uij，(1)i2(2)ijSS 2SS (1)12(2)151SS (1)42(2)451SS (1)52(2)53同理(2)(3)(2)(3)SS U021594608942036021150 U02672608942036021150 U(4)5444414311543215432124221S (4)從v1到v3的最短路長度 8