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

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