賦權(quán)圖的最短通路4-10

1、1 設(shè)設(shè)G=G=( (V,E)V,E)是有限圖是有限圖, ,如果對(duì)如果對(duì)E E中的每一條邊中的每一條邊e,e,都有一個(gè)實(shí)數(shù)都有一個(gè)實(shí)數(shù)W W( (e e) )附著其上附著其上, ,則稱則稱G G為為賦權(quán)圖賦權(quán)圖, ,則則稱稱W W( (e e) )為邊為邊e e的的權(quán)權(quán). .1 1、賦權(quán)圖、賦權(quán)圖例例 右圖就是一個(gè)右圖就是一個(gè)賦權(quán)圖賦權(quán)圖. .dceab141 1138129105 67賦權(quán)圖的最短通路賦權(quán)圖的最短通路 設(shè)賦權(quán)圖設(shè)賦權(quán)圖 G=( G=(V V, ,E E),u,v),u,vV V, ,從從u u到到v v所帶權(quán)所帶權(quán)的總和最小的通路的總和最小的通路, ,稱為稱為u u到到v v

2、的的最短通路最短通路. .對(duì)于賦權(quán)圖對(duì)于賦權(quán)圖 G=( G=(V V, ,E E) ), ,規(guī)定規(guī)定: :2例例4 如何求一權(quán)圖中任意兩點(diǎn)間的最短路？這如何求一權(quán)圖中任意兩點(diǎn)間的最短路？這里介紹里介紹狄克斯特洛算法狄克斯特洛算法(Dijkstras algorthm.)(Dijkstras algorthm.)2 2、問題與求法、問題與求法53、迪克斯特洛算法、迪克斯特洛算法6T Tazt權(quán)和最小記為權(quán)和最小記為D DT T(t)(t)7a acece權(quán)和為權(quán)和為1010T T例例8910定理定理 在賦權(quán)圖在賦權(quán)圖G=(V,E)G=(V,E)中中, ,起點(diǎn)起點(diǎn)a aV-T,V-T,設(shè)目標(biāo)集設(shè)目

3、標(biāo)集 T=t T=t1 1,t,t2 2, ,t,tn n,且且t t1 1為為T T中指標(biāo)最小者中指標(biāo)最小者, , 即即D DT T(t(t1 1)= minD)= minDT T(t(t1 1),D),DT T(t(t2 2),),D,DT T(t(tn n),), 則則a a到到t t1 1的最短通路的權(quán)和為的最短通路的權(quán)和為D DT T(t(t1 1).).證明證明 采用反證法采用反證法. .證證明思路如右圖所示明思路如右圖所示. .D DT T(t(t2 2) )W(aW(av v1 1v v2 2t t2 2)d d D DT T(t(t1 1) )學(xué)會(huì)多畫圖學(xué)會(huì)多畫圖, ,多從圖

4、形直觀上來看多從圖形直觀上來看. .d d=W(a=W(av v1 1v v2 2t t2 2t t1 1) )T Tat t1 1t t2 2D DT T(t(t1 1) )D DT T(t(t2 2) )v1 1v2 2若若d d D DT T(t(t1 1) ), ,即即黃色線黃色線比比紫色線紫色線短短, ,則從圖形直觀上則有則從圖形直觀上則有與與D DT T(t(t1 1) )的最短性相的最短性相矛盾！矛盾！定理定理 在有限賦權(quán)圖在有限賦權(quán)圖G=(V,E)G=(V,E)中中, ,頂點(diǎn)頂點(diǎn)a a為為起點(diǎn)起點(diǎn),|,|V|=n+1,V|=n+1, 遞歸地定義遞歸地定義目標(biāo)集目標(biāo)集 T T1

5、1=V-a=V-a, ,T Ti+1i+1=T=Ti i-t-ti i 即即 T Ti i=t=ti i,t,ti+1i+1, ,t,tn n(i=1,2,(i=1,2,n),n) 其中其中t ti i為為T Ti i中指標(biāo)最小者中指標(biāo)最小者, , 即即 D DT Ti i(t(ti i)= minD)= minDT Ti i(t(ti i),D),DT Ti i(t(ti+1i+1),),D,DT Ti i(t(tn n).). 則則 D DT Ti+1i+1(t)(t)D DT Ti i(t),(t),當(dāng)當(dāng)t t與與t ti i不鄰接不鄰接minDminDT Ti i(t),D(t),DT

6、 Ti i(t(ti i)+W(t)+W(ti i,t),t),當(dāng)當(dāng)t t與與t ti i鄰接鄰接= =(i=1,2,(i=1,2,n-1),n-1)證明證明T Ti iat ti it tD DT Ti+1i+1(t)=(t)=D DT Ti i(t)(t)T Ti+1i+1當(dāng)當(dāng)t t與與t ti i不鄰接不鄰接如右圖所示可知如右圖所示可知D DT Ti+1i+1(t)=D(t)=DT Ti i(t)(t)T Ti iat ti it tD DT Ti i(t)(t)T Ti+1i+1D DT Ti i(t(ti i) )如由圖所示，如由圖所示，設(shè)設(shè)黃線黃線為為a a到到t ti i的的最短

7、路徑最短路徑若存在若存在綠色綠色邊邊則則黃線黃線與與綠線綠線也構(gòu)成從也構(gòu)成從a a到到t t的一條路徑的一條路徑. .由各由各T Ti i的構(gòu)造過程知的構(gòu)造過程知, ,則存在則存在一條從一條從a a發(fā)的發(fā)的粉色粉色的最短路徑的最短路徑. .最終最終, , 從從a a出發(fā)的到出發(fā)的到t t的的粉色粉色路徑的權(quán)和路徑的權(quán)和 從從a a出發(fā)的到出發(fā)的到t t的的黃色黃色路徑的權(quán)和路徑的權(quán)和當(dāng)當(dāng)t t與與t t1 1鄰接時(shí)鄰接時(shí)W(tW(ti i,t),t)T Ti iat ti it tD DT Ti i(t)(t)T Ti+1i+1D DT Ti i(t(ti i) )+ +W(tW(ti i,t

8、),t)=min=minD DT Ti i(t)(t), ,D DT Ti i(t(ti i) )+ +W(tW(ti i,t),t), D DT Ti+1i+1(t)(t)當(dāng)當(dāng)t t與與t ti i鄰接時(shí)鄰接時(shí), ,由上面的分析可知由上面的分析可知, ,1617181920 當(dāng)我們比較熟練地掌握了狄克斯特洛算法后當(dāng)我們比較熟練地掌握了狄克斯特洛算法后, ,可用可用列表法列表法來求最短路來求最短路, ,它使求解過程顯得十分它使求解過程顯得十分簡(jiǎn)潔簡(jiǎn)潔. .下面以一例來介紹此法下面以一例來介紹此法. .例例 求右圖中求右圖中a a到到z z的最短路及其長(zhǎng)度的最短路及其長(zhǎng)度21方法：方法：( (1

9、 1) )先把先把T T1 1= =V V-a-a中的點(diǎn)寫在第一行上，把這些點(diǎn)中的點(diǎn)寫在第一行上，把這些點(diǎn)關(guān)于關(guān)于a a的權(quán)相應(yīng)地寫在第二行上的權(quán)相應(yīng)地寫在第二行上, ,并圈出其中最小并圈出其中最小者者b,b,相應(yīng)值為相應(yīng)值為1 1. .( (2)2)令令T T2 2= =T T1 1-b-b , ,在第三行上先標(biāo)出在第三行上先標(biāo)出T T1 1中與中與b b不鄰接不鄰接的點(diǎn)的點(diǎn)d,e,g,h, i, zd,e,g,h, i, z，對(duì)于，對(duì)于S S1 1中與中與b b 鄰接的點(diǎn)鄰接的點(diǎn)c,f,c,f,則用則用1+1+W W(b,c),1+ (b,c),1+ W W(b,f)(b,f)與第二行與第

10、二行c,fc,f的值的值1010與與比較比較, ,然后取最小者寫在第三行的相應(yīng)位置然后取最小者寫在第三行的相應(yīng)位置, ,并圈出并圈出最小點(diǎn)最小點(diǎn)e e及相應(yīng)值及相應(yīng)值3 3. .( (3)3)令令T T3 3= =T T2 2-e,-e,并其上的點(diǎn)寫在第并其上的點(diǎn)寫在第4 4行上行上, ,重復(fù)重復(fù)( (2).2).如此繼續(xù)下去如此繼續(xù)下去, ,直至直至z z成為某個(gè)目標(biāo)集的最小值為止成為某個(gè)目標(biāo)集的最小值為止. .22( (4 4) )由表可得最短路的長(zhǎng)度為由表可得最短路的長(zhǎng)度為1 15 5. .要得到最短路，要得到最短路，可以用可以用逆向檢查法逆向檢查法：從：從Z Z開始，往上檢查，直止開始，往上檢查，直止z z的值發(fā)生變化為止，在此行中找到最小者，然的值發(fā)生變化為止，在此行中找到最小者，然后由此最小者開始往上檢查，直止發(fā)生變化，后由此最小者開始往上檢查，直止發(fā)生變化，在此行中找最小者，重復(fù)這一過程直止到在此行中找最小者，重復(fù)這一過程直止到a a為止為止. .最后倒著把最小者