第四章圖論-2ppt課件

1、第三節(jié) 最短路問題一、標(biāo)號(hào)法一、標(biāo)號(hào)法 兩個(gè)固定點(diǎn)之間的最短路兩個(gè)固定點(diǎn)之間的最短路 二、距離矩陣法二、距離矩陣法 任意點(diǎn)之間的最短路任意點(diǎn)之間的最短路 標(biāo)號(hào)法標(biāo)號(hào)法計(jì)算步驟 （1）. 初始化 （永久標(biāo)號(hào)P，臨時(shí)標(biāo)號(hào)T） 設(shè)：起點(diǎn)設(shè)：起點(diǎn)VsVs，終點(diǎn)，終點(diǎn)VtVt，其他點(diǎn)，其他點(diǎn)ViVi起點(diǎn)起點(diǎn)VsVs： P(VS)=0P(VS)=0其他點(diǎn)其他點(diǎn)ViVi：T(Vi)=T(Vi)=計(jì)算停止判別標(biāo)準(zhǔn)：終點(diǎn)計(jì)算停止判別標(biāo)準(zhǔn)：終點(diǎn)VtVt獲得了獲得了P P標(biāo)號(hào)永久標(biāo)號(hào)）標(biāo)號(hào)永久標(biāo)號(hào)）例例V1V2V3V462148初始化初始化V1標(biāo)上標(biāo)上P標(biāo)號(hào)，標(biāo)號(hào)，P(V1)=0其他節(jié)點(diǎn)標(biāo)上其他節(jié)點(diǎn)標(biāo)上T標(biāo)號(hào)：標(biāo)號(hào)

2、：T(V2)=, T(V3)= T(V4)=P(V1)=0T(V2)=T(V3)=T(V4)= （2 2）. . 計(jì)算、修改計(jì)算、修改T T標(biāo)號(hào)標(biāo)號(hào) 設(shè)剛得到設(shè)剛得到P P標(biāo)號(hào)的節(jié)點(diǎn)為標(biāo)號(hào)的節(jié)點(diǎn)為ViVi，考慮所有與，考慮所有與ViVi相聯(lián)的相聯(lián)的T T標(biāo)號(hào)點(diǎn)標(biāo)號(hào)點(diǎn)VjVj，修改，修改VjVj的的T T標(biāo)號(hào)標(biāo)號(hào) ijdiPjTjT)(),(min)(P(Vi)V1V2V3V462148修改修改T T標(biāo)號(hào)：標(biāo)號(hào)：V1V1節(jié)點(diǎn)為剛得到節(jié)點(diǎn)為剛得到P P標(biāo)號(hào)的節(jié)點(diǎn)標(biāo)號(hào)的節(jié)點(diǎn)與之相連的節(jié)點(diǎn)是與之相連的節(jié)點(diǎn)是V2V2、V3V3T(V2)=min(,P(V1)+d12) =min(,0+6)=6P(V1)

3、=0T(V3)=min(,P(V1)+d13) =min(,0+2)=2P(V1)=0T(V2)=6T(V3)=2T(V4)=ijidVPjTjT)(),(min)( （3 3）. .確定確定P P標(biāo)號(hào)標(biāo)號(hào)在所有在所有T T標(biāo)號(hào)節(jié)點(diǎn)中，選擇標(biāo)號(hào)最小的節(jié)點(diǎn)，標(biāo)號(hào)節(jié)點(diǎn)中，選擇標(biāo)號(hào)最小的節(jié)點(diǎn)，將其將其T T標(biāo)號(hào)改為標(biāo)號(hào)改為P P標(biāo)號(hào)。標(biāo)號(hào)。V1V2V3V462148T(V4)=T(V2)=6T(V3)=2V3V3節(jié)點(diǎn)節(jié)點(diǎn)T T標(biāo)號(hào)值最小，標(biāo)號(hào)值最小，將其修改成將其修改成P P標(biāo)號(hào)標(biāo)號(hào)P(V3)=2P(V1)=0T(V2)=6T(V3)=2T(V4)=P(V3)=2 （4 4）. .重復(fù)重復(fù)2323步

4、驟，直到終點(diǎn)得到步驟，直到終點(diǎn)得到永久永久P P標(biāo)號(hào)。標(biāo)號(hào)。V1V2V3V462148修改修改T T標(biāo)號(hào)：標(biāo)號(hào)：V3V3節(jié)點(diǎn)為剛得到節(jié)點(diǎn)為剛得到P P標(biāo)號(hào)的節(jié)點(diǎn)標(biāo)號(hào)的節(jié)點(diǎn)與之相連的節(jié)點(diǎn)是與之相連的節(jié)點(diǎn)是V2V2、V4V4T(V2)=min(6,P(V3)+d32) =min(6,2+1)=3P(V3)=2T(V4)=min(,P(V3)+d34) =min(,2+8)=10P(V1)=0T(V2)=3P(V3)=2T(V4)=10V1V2V3V462188T(V2)=3T(V4)=10V2V2節(jié)點(diǎn)節(jié)點(diǎn)T T標(biāo)號(hào)值最小，標(biāo)號(hào)值最小，將其修改成將其修改成P P標(biāo)號(hào)標(biāo)號(hào)P(V2)=3P(V1)=0T

5、(V2)=3T(V4)=10P(V3)=2P(V2)=3V1V2V3V462188修改修改T T標(biāo)號(hào)：標(biāo)號(hào)：V2V2節(jié)點(diǎn)為剛得到節(jié)點(diǎn)為剛得到P P標(biāo)號(hào)的節(jié)點(diǎn)標(biāo)號(hào)的節(jié)點(diǎn)與之相連的節(jié)點(diǎn)是與之相連的節(jié)點(diǎn)是V4V4T(V4)=min(10,P(V2)+d24) =min(10,3+8)=10P(V2)=3P(V1)=0P(V2)=3P(V3)=2T(V4)=10這時(shí)只有一個(gè)這時(shí)只有一個(gè)T T標(biāo)號(hào)節(jié)點(diǎn)：標(biāo)號(hào)節(jié)點(diǎn)：V4V4將將V4V4的的T T標(biāo)號(hào)改成標(biāo)號(hào)改成P P標(biāo)號(hào)標(biāo)號(hào)V1V2V3V462148P(V4)=7計(jì)算停止，從計(jì)算停止，從V1V1到到V4V4的的最短路為最短路為7 7個(gè)單位。個(gè)單位。P(V1

6、)=0P(V2)=3P(V3)=2T(V4)=7P(V4)=7 最短路徑追蹤：最短路徑追蹤： P(V4)=P(V2)+d24P(V4)=P(V2)+d24，記錄，記錄V2V4V2V4 P(V2)= P(V3)+d32P(V2)= P(V3)+d32，記錄，記錄V3V2V3V2 P(V3)= P(V1)+d13P(V3)= P(V1)+d13，記錄，記錄V1V3V1V3 所以，從所以，從V1V4V1V4的最短路徑為的最短路徑為 V1V3V2V4V1V3V2V4最短路問題的兩個(gè)結(jié)果：最短路權(quán) 最短路徑V1V2V3V462148 最短路徑追蹤：最短路徑追蹤： P(V4)=P(V2)+d24，記，記錄

7、錄V2V4 P(V2)= P(V3)+d32，記錄記錄V3V2 P(V3)= P(V1)+d13，記錄記錄V1V3 所以，從所以，從V1V4的最的最短路徑為短路徑為 V1V3V2V4計(jì)算停止判別標(biāo)準(zhǔn)：計(jì)算停止判別標(biāo)準(zhǔn)：對于求對于求VSVtVSVt的最短路，的最短路，VtVt標(biāo)上標(biāo)上P P標(biāo)號(hào)時(shí)計(jì)算停止；標(biāo)號(hào)時(shí)計(jì)算停止；對于求對于求VSVS所有點(diǎn)的最短路，所有所有點(diǎn)的最短路，所有點(diǎn)標(biāo)上點(diǎn)標(biāo)上P P標(biāo)號(hào)時(shí)計(jì)算停止。標(biāo)號(hào)時(shí)計(jì)算停止。 對于標(biāo)號(hào)法的說明對于標(biāo)號(hào)法的說明 （1 1）. . 路權(quán)為負(fù)值時(shí)失效交通網(wǎng)絡(luò)路權(quán)為負(fù)值時(shí)失效交通網(wǎng)絡(luò)中一般不存在）中一般不存在） （2 2）. . 對于無向圖對于無向圖

8、（將原圖中的每（將原圖中的每條邊視為由方向相反的兩條弧組成，條邊視為由方向相反的兩條弧組成，其權(quán)相等。其權(quán)相等。V1V2V3V462148V1V2V3V4621484無向圖的處理：將原圖中的每條邊視為由方向相反的兩條無向圖的處理：將原圖中的每條邊視為由方向相反的兩條 弧組成，其權(quán)相等弧組成，其權(quán)相等距離矩陣法距離矩陣法 適用條件：任意點(diǎn)之間的最短路 1、構(gòu)造距離矩陣、構(gòu)造距離矩陣D=dijD=dij之間直接連接權(quán)值之間不直接連接ji, ji, ji 0ijdV1V2V3V4621480 8 0 1 4 0 2 6 00DDijDij的含義：當(dāng)前從的含義：當(dāng)前從i i節(jié)點(diǎn)直接到節(jié)點(diǎn)直接到j(luò) j節(jié)

9、點(diǎn)的距離節(jié)點(diǎn)的距離 2、矩陣迭代計(jì)算、矩陣迭代計(jì)算11iijidDnkdddikjiikiij, 2 , 1,min1 3、終止判別條件、終止判別條件（n為節(jié)點(diǎn)數(shù)量）為節(jié)點(diǎn)數(shù)量）1mmDDV1V2V3V4621480 8 0 1 4 0 2 6 00Dnkdddikjiikiij, 2 , 1,min10 8 0 1 4 0 10 2 3 01D3 , 12 , 06 , 60min , , ,min042014032013022012012011112dddddddddK=1K=2K=3K=4V1V2V3V4621480 8 0 1 4 0 2 6 00D0 8 0 1 4 0 10 2 3 01D0 5 0 1