離散數(shù)學(xué)CH04_圖論_最短路徑與關(guān)鍵路徑

離散數(shù)學(xué)DiscreteMathematics,計(jì)算機(jī)與信息工程學(xué)院,第4章圖論,內(nèi)容提要,圖的基本概念,4.1,連通圖,4.3,4.4,圖的矩陣表示,路和回路,4.2,內(nèi)容提要,歐拉圖和哈密頓圖,4.5,二部圖及匹配,4.7,4.8,平面圖,樹(shù),4.6,定義：設(shè)G=(V，E，)為無(wú)向簡(jiǎn)單圖，對(duì)于每一條邊eE，均有一個(gè)正實(shí)數(shù)W(e)與之對(duì)應(yīng)，稱w為G的權(quán)函數(shù)，并稱G為帶有權(quán)W的圖，又稱賦權(quán)圖，權(quán)也稱為邊的長(zhǎng)度。,4.5最短路徑及關(guān)鍵路徑,邊(vi,vj)的權(quán),帶權(quán)圖,求給定兩點(diǎn)間的最短距離兩點(diǎn)之間的最短路徑問(wèn)題,求從某個(gè)源點(diǎn)到其余各點(diǎn)的最短路徑,每一對(duì)頂點(diǎn)之間的最短路徑,4.5最短路徑及關(guān)鍵路徑,求從源點(diǎn)到其余各點(diǎn)的最短路徑的算法的基本思想:,依最短路徑的長(zhǎng)度遞增的次序求得各條路徑,源點(diǎn),v1,其中，從源點(diǎn)到頂點(diǎn)v1的最短路徑是所有最短路徑中長(zhǎng)度最短者。,v2,4.5最短路徑及關(guān)鍵路徑,在這條路徑上，必定只含一條弧，并且這條弧的權(quán)值最小。,下一條路徑長(zhǎng)度次短的最短路徑的特點(diǎn)：,路徑長(zhǎng)度最短的最短路徑的特點(diǎn)：,它只可能有兩種情況：或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)；或者是從源點(diǎn)經(jīng)過(guò)頂點(diǎn)v1，再到達(dá)該頂點(diǎn)(由兩條弧組成)。,4.5最短路徑及關(guān)鍵路徑,其余最短路徑的特點(diǎn)：,再下一條路徑長(zhǎng)度次短的最短路徑的特點(diǎn):,它可能有三種情況：或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)；或者是從源點(diǎn)經(jīng)過(guò)頂點(diǎn)v1，再到達(dá)該頂點(diǎn)(由兩條弧組成)；或者是從源點(diǎn)經(jīng)過(guò)頂點(diǎn)v2，再到達(dá)該頂點(diǎn)。,它或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)；或者是從源點(diǎn)經(jīng)過(guò)已求得最短路徑的頂點(diǎn)，再到達(dá)該頂點(diǎn)。,4.5最短路徑及關(guān)鍵路徑,從源點(diǎn)到其余各點(diǎn)的最短路徑Dijkstra算法（1959）設(shè)G有n個(gè)頂點(diǎn)；邊的長(zhǎng)度ij0；若結(jié)點(diǎn)vi和vj沒(méi)有邊相連(不是鄰接點(diǎn))，則令ij=，對(duì)每個(gè)結(jié)點(diǎn)vi，令ij=0。,4.5最短路徑及關(guān)鍵路徑,將頂點(diǎn)集V分成兩部分，一部分成為具有P（永久性）標(biāo)號(hào)的集合，另一部分成為具有T（暫時(shí)性）標(biāo)號(hào)的集合。所謂結(jié)點(diǎn)v的P標(biāo)號(hào)是指從v1到v的最短路徑的長(zhǎng)度；而頂點(diǎn)u的T標(biāo)號(hào)是指從v1到u某條路徑的長(zhǎng)度。Dijkstras算法首先將v1取為P標(biāo)號(hào)，其余結(jié)點(diǎn)取為T(mén)標(biāo)號(hào)，然后逐步將具有T標(biāo)號(hào)的結(jié)點(diǎn)改為P標(biāo)號(hào)。當(dāng)結(jié)點(diǎn)vn已被改為P標(biāo)號(hào)時(shí)，就找到了一條從v1到vn的最短路徑。,4.5最短路徑及關(guān)鍵路徑,Dijkstras基本思路：,Step1:初始化：將v1置為P標(biāo)號(hào)，d(v1)=0，P=v1，vi(i1)置vi為T(mén)標(biāo)號(hào)，即T=V-P，且d(vi)=W(v1,vi)若viadjvid(vi)=else,4.5最短路徑及關(guān)鍵路徑,Step2:找最小尋找具有最小值的T標(biāo)號(hào)的結(jié)點(diǎn)。若為vl，則將vl的T標(biāo)號(hào)改為P標(biāo)號(hào)，且P=Pvl，T=T-vl。Step3：修改修改與vl相鄰的結(jié)點(diǎn)的T標(biāo)號(hào)的值。viT：d(vi)=,4.5最短路徑及關(guān)鍵路徑,Step4：重復(fù)（2）和（3），直到vn改為P標(biāo)號(hào)為止?！纠吭嚽鬅o(wú)向賦權(quán)圖中v1到v6的最短路徑。,4.5最短路徑及關(guān)鍵路徑,P=v1T=v2,v3,v4,v5,v6,4.5最短路徑及關(guān)鍵路徑,P=v1,v2T=v3,v4,v5,v6,4.5最短路徑及關(guān)鍵路徑,P=v1,v2,v3T=v4,v5,v6,4.5最短路徑及關(guān)鍵路徑,P=v1,v2,v3,v5T=v4,v6,4.5最短路徑及關(guān)鍵路徑,P=v1,v2,v3,v5,v4T=v6,4.5最短路徑及關(guān)鍵路徑,(v1),0,(v1,v2),P=v1,v2,v3,v5v4,v6T=,1,(v1,v2,v3,v5),(v1,v2,v3),3,4,(v1,v2,v3,v5,v4),7,9,4.5最短路徑及關(guān)鍵路徑,10(v5)第1短,step1,50,30,100,10,20(v4)第2短,step2,50,30,20,30(v3)第3短,step3,40,30,35(v2)第4短,step4,35,50,45(v6)第5短,step5,45,/V1,/V5,/V1,/V3,/V2,4.5最短路徑及關(guān)鍵路徑,2(v2)第1短,step1,2,5,3,3(v4)第2短,step2,4,3,4(v3)第3短,step3,8,4,7(v5)第4短,step4,7,9,8(v6)第5短,step5,8,step6,13(v7)第6短,13,9,9,14,4.5最短路徑及關(guān)鍵路徑,試用Dijkstra算法求下列簡(jiǎn)單無(wú)向賦權(quán)圖中V1到V11的最短路徑。,4.5最短路徑及關(guān)鍵路徑,求任意兩點(diǎn)間最短距離的Floyd算法基本思想：從vi到vj的所有可能存在的路徑中，選出一條長(zhǎng)度最短的路徑。,4.5最短路徑及關(guān)鍵路徑,求每一對(duì)頂點(diǎn)之間的最短路徑,在實(shí)施一個(gè)工程計(jì)劃時(shí)，若將整個(gè)工程分成若干工序，有些工序可以同時(shí)實(shí)施，有些工序必須在完成另一些工序后才能實(shí)施，工序之間的次序關(guān)系可以用有向圖來(lái)表示，這種有向圖稱為PERT圖。,4.5最短路徑及關(guān)鍵路徑,關(guān)鍵路徑問(wèn)題PERT圖（計(jì)劃評(píng)審技術(shù)圖）,4.5最短路徑及關(guān)鍵路徑,關(guān)鍵路徑問(wèn)題PERT圖（計(jì)劃評(píng)審技術(shù)圖）,4.5最短路徑及關(guān)鍵路徑,關(guān)鍵路徑問(wèn)題PERT圖（計(jì)劃評(píng)審技術(shù)圖）,在PERT圖中求關(guān)鍵路徑，就是從始點(diǎn)到終點(diǎn)的一條最長(zhǎng)路徑，通過(guò)求各頂點(diǎn)的最早完成時(shí)間來(lái)求關(guān)鍵路徑。,4.5最短路徑及關(guān)鍵路徑,關(guān)鍵路徑問(wèn)題PERT圖（計(jì)劃評(píng)審技術(shù)圖）,PERT圖最早完成時(shí)間,4.5最短路徑及關(guān)鍵路徑,PERT圖最晚完成時(shí)間,4.5最短路徑及關(guān)鍵路徑,PERT圖緩沖時(shí)