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

1、離散數(shù)學(xué)離散數(shù)學(xué)discrete mathematics計(jì)算機(jī)與信息工程學(xué)院計(jì)算機(jī)與信息工程學(xué)院第第4章章 圖圖 論論內(nèi)容提要內(nèi)容提要圖的基本概念圖的基本概念4.1連通圖連通圖4.34.4圖的矩陣表示圖的矩陣表示路和回路路和回路4.2內(nèi)容提要內(nèi)容提要?dú)W拉圖和哈密頓圖歐拉圖和哈密頓圖4.5二部圖及匹配二部圖及匹配4.74.8平面圖平面圖樹樹4.6n定義：定義：設(shè)設(shè)g=(vg=(v，e e， ) )為無向簡單圖，對(duì)于每一條邊為無向簡單圖，對(duì)于每一條邊eeee，均有一，均有一個(gè)正實(shí)數(shù)個(gè)正實(shí)數(shù)w(e)w(e)與之對(duì)應(yīng)，稱與之對(duì)應(yīng)，稱w w為為gg的權(quán)函數(shù)，并稱的權(quán)函數(shù)，并稱gg為帶有為帶有權(quán)權(quán)ww的圖

2、，又稱賦權(quán)圖，權(quán)也稱為邊的長度。的圖，又稱賦權(quán)圖，權(quán)也稱為邊的長度。4.5 4.5 最短路徑及關(guān)鍵路徑最短路徑及關(guān)鍵路徑邊邊(vi,vj)的權(quán)的權(quán)帶權(quán)圖帶權(quán)圖求給定兩點(diǎn)間的最短距離求給定兩點(diǎn)間的最短距離兩點(diǎn)之間的最短路徑問題兩點(diǎn)之間的最短路徑問題 求從某個(gè)源點(diǎn)到其余各點(diǎn)的最短路徑求從某個(gè)源點(diǎn)到其余各點(diǎn)的最短路徑每一對(duì)頂點(diǎn)之間的最短路徑每一對(duì)頂點(diǎn)之間的最短路徑4.5 4.5 最短路徑及關(guān)鍵路徑最短路徑及關(guān)鍵路徑 求求從源點(diǎn)到其余各點(diǎn)的最短路徑從源點(diǎn)到其余各點(diǎn)的最短路徑的算法的基本思想的算法的基本思想: :依最短路徑的長度遞增的次序求得各條路徑依最短路徑的長度遞增的次序求得各條路徑源點(diǎn)源點(diǎn)v1其中

3、，從源點(diǎn)到頂點(diǎn)從源點(diǎn)到頂點(diǎn)v v1 1的的最短路徑最短路徑是所有最短路徑中長度最短者。v24.5 4.5 最短路徑及關(guān)鍵路徑最短路徑及關(guān)鍵路徑在這條路徑上，必定只含一條弧，并且這條弧的權(quán)值最小。 下一條路徑長度次短的最短路徑的特點(diǎn)：路徑長度最短的最短路徑最短路徑的特點(diǎn)： 它只可能有兩種情況：或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)； 或者是從源點(diǎn)經(jīng)過頂點(diǎn)v1，再到達(dá)該頂點(diǎn)(由兩條弧組成)。4.5 4.5 最短路徑及關(guān)鍵路徑最短路徑及關(guān)鍵路徑其余最短路徑的特點(diǎn)：再下一條路徑長度次短的最短路徑最短路徑的特點(diǎn):它可能有三種情況：或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)； 或者是從源點(diǎn)經(jīng)過頂點(diǎn)v1，再到達(dá)該頂

4、點(diǎn)(由兩條弧組成)；或者是從源點(diǎn)經(jīng)過頂點(diǎn)v2，再到達(dá)該頂點(diǎn)。它或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)； 或者是從源點(diǎn)經(jīng)過已求得最短路徑的頂點(diǎn)，再到達(dá)該頂點(diǎn)。4.5 4.5 最短路徑及關(guān)鍵路徑最短路徑及關(guān)鍵路徑 從源點(diǎn)到其余各點(diǎn)的最短路徑從源點(diǎn)到其余各點(diǎn)的最短路徑 dijkstradijkstra算法算法（19591959） 設(shè)設(shè)gg有有n n個(gè)頂點(diǎn)；邊的長度個(gè)頂點(diǎn)；邊的長度ij0ij0；若結(jié)點(diǎn)；若結(jié)點(diǎn)vivi和和vjvj沒有邊相連沒有邊相連( (不是鄰接點(diǎn)不是鄰接點(diǎn)) )，則令，則令ij=ij=，對(duì)每個(gè)，對(duì)每個(gè)結(jié)點(diǎn)結(jié)點(diǎn)vivi，令，令ij=0ij=0。4.5 4.5 最短路徑及關(guān)鍵路徑最短路徑及

5、關(guān)鍵路徑 將頂點(diǎn)集將頂點(diǎn)集v v分成兩部分，一部分成為具有分成兩部分，一部分成為具有p p（永久性）標(biāo)（永久性）標(biāo)號(hào)的集合，另一部分成為具有號(hào)的集合，另一部分成為具有t t（暫時(shí)性）標(biāo)號(hào)的集合。所（暫時(shí)性）標(biāo)號(hào)的集合。所謂結(jié)點(diǎn)謂結(jié)點(diǎn)v v的的p p標(biāo)號(hào)是指從標(biāo)號(hào)是指從v1v1到到v v的最短路徑的長度；而頂點(diǎn)的最短路徑的長度；而頂點(diǎn)u u的的t t標(biāo)號(hào)是指從標(biāo)號(hào)是指從v1v1到到u u某條路徑的長度。某條路徑的長度。 dijkstras算法首先算法首先將將v1v1取為取為p p標(biāo)號(hào)，其余結(jié)點(diǎn)取為標(biāo)號(hào)，其余結(jié)點(diǎn)取為t t標(biāo)號(hào)，然后逐步將具有標(biāo)號(hào)，然后逐步將具有t t標(biāo)標(biāo)號(hào)的結(jié)點(diǎn)改為號(hào)的結(jié)點(diǎn)改為p

6、 p標(biāo)號(hào)。當(dāng)結(jié)點(diǎn)標(biāo)號(hào)。當(dāng)結(jié)點(diǎn)vnvn已被改為已被改為p p標(biāo)號(hào)時(shí)，就找到標(biāo)號(hào)時(shí)，就找到了一條從了一條從v1v1到到vnvn的最短路徑。的最短路徑。4.5 4.5 最短路徑及關(guān)鍵路徑最短路徑及關(guān)鍵路徑dijkstrasdijkstras基本思路：基本思路：nstep1:step1:初始化：將初始化：將v v1 1置為置為p p標(biāo)號(hào)，標(biāo)號(hào)，d(vd(v1 1)=0)=0，p=vp=v1 1 ， v vi i(i1)(i1)置置v vi i 為為t t標(biāo)號(hào)，即標(biāo)號(hào)，即t=v-pt=v-p，且，且 d(vd(vi i)=w(v)=w(v1 1, v, vi i) ) 若若v vi iadjvadjvi

7、 i d(v d(vi i)= else)= else4.5 4.5 最短路徑及關(guān)鍵路徑最短路徑及關(guān)鍵路徑nstep2:step2:找最小找最小尋找具有最小值的尋找具有最小值的t t標(biāo)號(hào)的結(jié)點(diǎn)。若為標(biāo)號(hào)的結(jié)點(diǎn)。若為v vl l，則將，則將v vl l的的t t標(biāo)號(hào)改為標(biāo)號(hào)改為p p標(biāo)號(hào)，且標(biāo)號(hào)，且p=pvp=pvl l ，t=t-vt=t-vl l 。nstep3step3：修改：修改修改與修改與vlvl 相鄰的結(jié)點(diǎn)的相鄰的結(jié)點(diǎn)的t t標(biāo)號(hào)的值。標(biāo)號(hào)的值。 vivi t t ： d(vi)=d(vi)=d(vl)+w(vl,vi) 若若d(vl)+w(vl,vi)d(vi)d(vi) 否則否則

8、4.5 4.5 最短路徑及關(guān)鍵路徑最短路徑及關(guān)鍵路徑n step4：重復(fù)（重復(fù)（2 2）和（）和（3 3），直到），直到v vn n改為改為p p標(biāo)號(hào)為止。標(biāo)號(hào)為止?！纠吭嚽鬅o向賦權(quán)圖中【例】試求無向賦權(quán)圖中v v1 1到到v v6 6的最短路徑。的最短路徑。 v2v47512v1v3v5v6412364.5 4.5 最短路徑及關(guān)鍵路徑最短路徑及關(guān)鍵路徑1(v1)04(v1)p=v1t=v2 , v3,v4,v5,v64.5 4.5 最短路徑及關(guān)鍵路徑最短路徑及關(guān)鍵路徑p=v1,v2t=v3,v4,v5,v6(v1)03(v1,v2)18(v1,v2)6(v1,v2)4.5 4.5 最短路徑

9、及關(guān)鍵路徑最短路徑及關(guān)鍵路徑p=v1,v2 , v3t=v4,v5,v6(v1)0(v1,v2)18(v1,v2)4(v1,v2, v3)34.5 4.5 最短路徑及關(guān)鍵路徑最短路徑及關(guān)鍵路徑p=v1,v2 , v3, v5t=v4,v6(v1)0(v1,v2)17(v1,v2 ,v3,v5)(v1,v2, v3)3410(v1,v2 ,v3,v5)4.5 4.5 最短路徑及關(guān)鍵路徑最短路徑及關(guān)鍵路徑p=v1,v2 , v3, v5 , v4t=v6(v1)0(v1,v2)1(v1,v2 ,v3,v5)(v1,v2, v3)349(v1,v2 ,v3,v5)74.5 4.5 最短路徑及關(guān)鍵路徑

10、最短路徑及關(guān)鍵路徑(v1)0(v1,v2)p=v1,v2 , v3, v5 v4 , v6t=1(v1,v2 ,v3,v5)(v1,v2, v3)34(v1,v2 ,v3,v5 ,v4)794.5 4.5 最短路徑及關(guān)鍵路徑最短路徑及關(guān)鍵路徑10(v5)第第1短短v1v5v4v2v3v610101002050205030510v2 v3 v4 v5 v6step150 30 100 1020(v4)第第2 2短短step250 30 2030(v3)第第3短短step340 3035(v2)第第4短短step4355045(v6)第第5短短step545/v1/v5/v1/v3/v24.5 4

11、.5 最短路徑及關(guān)鍵路徑最短路徑及關(guān)鍵路徑2(v2)第第1短短v2 v3 v4 v5 v6 v7step1253 3(v4)第第2 2短短step2434(v3)第第3短短step3847(v5)第第4短短step4798(v6)第第5短短step58v2v12v3v6v7v4v553125753517step613(v7)第第6短短1399144.5 4.5 最短路徑及關(guān)鍵路徑最短路徑及關(guān)鍵路徑n試用試用dijkstradijkstra算法求下列簡單無向賦權(quán)圖中算法求下列簡單無向賦權(quán)圖中v1v1到到v11v11的最短路徑。的最短路徑。 4.5 4.5 最短路徑及關(guān)鍵路徑最短路徑及關(guān)鍵路徑v1

12、 v2v5v4v10v8v7v11v3v6v92112919465397243116827 求任意兩點(diǎn)間最短距離的求任意兩點(diǎn)間最短距離的floydfloyd算法算法基本思想：從 vi 到 vj 的所有可能存在的路徑中，選出一條長度最 短的路徑。4.5 4.5 最短路徑及關(guān)鍵路徑最短路徑及關(guān)鍵路徑求每一對(duì)頂點(diǎn)之間的最短路徑在實(shí)施一個(gè)工程計(jì)劃時(shí)，若將整個(gè)工程分成若干在實(shí)施一個(gè)工程計(jì)劃時(shí)，若將整個(gè)工程分成若干工序，有些工序可以同時(shí)實(shí)施，有些工序必須在工序，有些工序可以同時(shí)實(shí)施，有些工序必須在完成另一些工序后才能實(shí)施，工序之間的次序關(guān)完成另一些工序后才能實(shí)施，工序之間的次序關(guān)系可以用有向圖來表示，這種

13、有向圖稱為系可以用有向圖來表示，這種有向圖稱為pertpert圖。圖。4.5 4.5 最短路徑及關(guān)鍵路徑最短路徑及關(guān)鍵路徑關(guān)鍵路徑問題關(guān)鍵路徑問題pertpert圖（計(jì)劃評(píng)審技術(shù)圖）圖（計(jì)劃評(píng)審技術(shù)圖）,dv evv定義：設(shè)為一個(gè)有向圖稱 |(,)dxvxvv xe v為 的后繼元集； |(,)dxvxvx ve v為 的先驅(qū)元集.4.5 4.5 最短路徑及關(guān)鍵路徑最短路徑及關(guān)鍵路徑關(guān)鍵路徑問題關(guān)鍵路徑問題pertpert圖（計(jì)劃評(píng)審技術(shù)圖）圖（計(jì)劃評(píng)審技術(shù)圖）,dv e wn設(shè)是一個(gè) 階有向帶權(quán)圖，滿足(1)(2)(3)0,0(4,)ijijddvwv是簡單圖；中無回路；有一個(gè)頂點(diǎn)入度為 稱

14、此頂點(diǎn)為始點(diǎn)； 有一個(gè)頂點(diǎn)出度為 ，稱此頂點(diǎn)為終點(diǎn)；記邊帶的，它一般權(quán)為表示時(shí)間；pertd則稱 為圖.4.5 4.5 最短路徑及關(guān)鍵路徑最短路徑及關(guān)鍵路徑關(guān)鍵路徑問題關(guān)鍵路徑問題pertpert圖（計(jì)劃評(píng)審技術(shù)圖）圖（計(jì)劃評(píng)審技術(shù)圖）在在pertpert圖中求關(guān)鍵路徑，就是從始點(diǎn)到終點(diǎn)的圖中求關(guān)鍵路徑，就是從始點(diǎn)到終點(diǎn)的一條最長路徑，通過求各頂點(diǎn)的最早完成時(shí)間來一條最長路徑，通過求各頂點(diǎn)的最早完成時(shí)間來求關(guān)鍵路徑。求關(guān)鍵路徑。4.5 4.5 最短路徑及關(guān)鍵路徑最短路徑及關(guān)鍵路徑關(guān)鍵路徑問題關(guān)鍵路徑問題pertpert圖（計(jì)劃評(píng)審技術(shù)圖）圖（計(jì)劃評(píng)審技術(shù)圖）pertpert圖圖最早完成時(shí)間最早

15、完成時(shí)間1()v自始點(diǎn) 記為開始沿最長路徑（按權(quán)計(jì)算）iivv到達(dá) 所需的時(shí)間，稱為 的最早完成時(shí)間.( ),1,2,., .ite vin記作11( )0,()ite vv i 顯然有的最早完成時(shí)間可按如下公式計(jì)算：()( )max ( ),2,3,., .jdivviiijte vte vwin1()nnnvte vvv終點(diǎn) 的最早完成時(shí)間就是從 到 的最長路徑的權(quán)。a（7 ）4.5 4.5 最短路徑及關(guān)鍵路徑最短路徑及關(guān)鍵路徑pertpert圖圖最晚完成時(shí)間最晚完成時(shí)間()()nnitl vte vinv由定義可知，；的最晚完成時(shí)間由下時(shí)，面公式計(jì)算：()( )max ( ),1,2,3

16、,.,1.jdiiiijvvtl vtl vwin1( ).niiivvvvtl v在保證終點(diǎn) 的最早完成時(shí)間不增加的條件下，自最遲到達(dá) 的時(shí)間稱為 的最晚完成時(shí)間，記作b（7 ）4.5 4.5 最短路徑及關(guān)鍵路徑最短路徑及關(guān)鍵路徑pertpert圖圖緩沖時(shí)間緩沖時(shí)間0,( )( )( )( )iiiiitl vte vlte vvtv 。稱為 由定義可知的緩沖時(shí)間，( )( )( ),1,2,., .iiits vtl vte vin記作0.tt在關(guān)鍵路徑上，任何工序如果耽誤了時(shí)間 ，整個(gè)工序就耽誤了時(shí)間 ，因而在關(guān)鍵路徑上各頂點(diǎn)的緩沖時(shí)間均為4.5 4.5 最短路徑及關(guān)鍵路徑最短路徑及關(guān)鍵

17、路徑pertpert圖舉例圖舉例例例 求圖中所示的求圖中所示的pertpert圖中各頂點(diǎn)的最早、最晚和緩沖圖中各頂點(diǎn)的最早、最晚和緩沖時(shí)間以及關(guān)鍵路徑。時(shí)間以及關(guān)鍵路徑。4.5 4.5 最短路徑及關(guān)鍵路徑最短路徑及關(guān)鍵路徑解：各點(diǎn)最早完成時(shí)間用公式(7a)計(jì)算：3412( )0;()max0 11;()max02,1 02;()max03,224;te vte vte vte v5678()max1 3,448;()max24,8 19;()max14,246;()max9 1,6612.te vte vte vte v4.5 4.5 最短路徑及關(guān)鍵路徑最短路徑及關(guān)鍵路徑b各點(diǎn)最晚完成時(shí)間用公式(7 )計(jì)算：7865()12;()min1266;()min12