離散數(shù)學CH04圖論最短路徑與關鍵路徑

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

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

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

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

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

6、 p標號。當結點標號。當結點vnvn已被改為已被改為p p標號時，就找到標號時，就找到了一條從了一條從v1v1到到vnvn的最短路徑。的最短路徑。4.5 4.5 最短路徑及關鍵路徑最短路徑及關鍵路徑dijkstrasdijkstras基本思路：基本思路：nstep1:step1:初始化：將初始化：將v v1 1置為置為p p標號，標號，d(vd(v1 1)=0)=0，p=vp=v1 1 ， v vi i(i1)(i1)置置v vi i 為為t t標號，即標號，即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 最短路徑及關鍵路徑最短路徑及關鍵路徑nstep2:step2:找最小找最小尋找具有最小值的尋找具有最小值的t t標號的結點。若為標號的結點。若為v vl l，則將，則將v vl l的的t t標號改為標號改為p p標號，且標號，且p=pvp=pvl l ，t=t-vt=t-vl l 。nstep3step3：修改：修改修改與修改與vlvl 相鄰的結點的相鄰的結點的t t標號的值。標號的值。 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 最短路徑及關鍵路徑最短路徑及關鍵路徑n step4：重復（重復（2 2）和（）和（3 3），直到），直到v vn n改為改為p p標號為止。標號為止。【例】試求無向賦權圖中【例】試求無向賦權圖中v v1 1到到v v6 6的最短路徑。的最短路徑。 v2v47512v1v3v5v6412364.5 4.5 最短路徑及關鍵路徑最短路徑及關鍵路徑1(v1)04(v1)p=v1t=v2 , v3,v4,v5,v64.5 4.5 最短路徑及關鍵路徑最短路徑及關鍵路徑p=v1,v2t=v3,v4,v5,v6(v1)03(v1,v2)18(v1,v2)6(v1,v2)4.5 4.5 最短路徑

9、及關鍵路徑最短路徑及關鍵路徑p=v1,v2 , v3t=v4,v5,v6(v1)0(v1,v2)18(v1,v2)4(v1,v2, v3)34.5 4.5 最短路徑及關鍵路徑最短路徑及關鍵路徑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 最短路徑及關鍵路徑最短路徑及關鍵路徑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 最短路徑及關鍵路徑

10、最短路徑及關鍵路徑(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 最短路徑及關鍵路徑最短路徑及關鍵路徑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 最短路徑及關鍵路徑最短路徑及關鍵路徑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 最短路徑及關鍵路徑最短路徑及關鍵路徑n試用試用dijkstradijkstra算法求下列簡單無向賦權圖中算法求下列簡單無向賦權圖中v1v1到到v11v11的最短路徑。的最短路徑。 4.5 4.5 最短路徑及關鍵路徑最短路徑及關鍵路徑v1

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

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

14、此頂點為始點； 有一個頂點出度為 ，稱此頂點為終點；記邊帶的，它一般權為表示時間；pertd則稱 為圖.4.5 4.5 最短路徑及關鍵路徑最短路徑及關鍵路徑關鍵路徑問題關鍵路徑問題pertpert圖（計劃評審技術圖）圖（計劃評審技術圖）在在pertpert圖中求關鍵路徑，就是從始點到終點的圖中求關鍵路徑，就是從始點到終點的一條最長路徑，通過求各頂點的最早完成時間來一條最長路徑，通過求各頂點的最早完成時間來求關鍵路徑。求關鍵路徑。4.5 4.5 最短路徑及關鍵路徑最短路徑及關鍵路徑關鍵路徑問題關鍵路徑問題pertpert圖（計劃評審技術圖）圖（計劃評審技術圖）pertpert圖圖最早完成時間最早

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

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

17、路徑pertpert圖舉例圖舉例例例 求圖中所示的求圖中所示的pertpert圖中各頂點的最早、最晚和緩沖圖中各頂點的最早、最晚和緩沖時間以及關鍵路徑。時間以及關鍵路徑。4.5 4.5 最短路徑及關鍵路徑最短路徑及關鍵路徑解：各點最早完成時間用公式(7a)計算：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 最短路徑及關鍵路徑最短路徑及關鍵路徑b各點最晚完成時間用公式(7 )計算：7865()12;()min1266;()min12