第二十九講關(guān)鍵路徑

1、數(shù),據(jù),結(jié),構(gòu),第,二十九,講,知,識,點,活動的最早開始時間、最遲開始時間,關(guān)鍵活動、關(guān)鍵路徑的確定,最短路徑的概念,從源點到各頂點最短路徑算法的描述,每兩個頂點間最短路徑的查找,重,點,關(guān)鍵路徑中各頂點與活動最早開始時間和,最遲開始時間的確定,從源點到各頂點最短路徑求解過程,數(shù),據(jù),結(jié),構(gòu),7,、在描述關(guān)鍵路徑的算法時，設(shè)活動,a,由弧,表示，持續(xù)時間記為,dut,，則,1,）事件,Vj,的最早出現(xiàn)時間,vej,從源點,V0,到某頂點,Vj,的最長路徑長度叫作事件,Vj,的,最早開始時間，,vej=maxvei+dut,，,?,T,必須在拓撲有序前提下進行,2,）活動,a,的最早開始時間,

2、eei,頂點,Vj,的最早出現(xiàn)時間,vej,決定了從,Vj,指出的各條邊,所代表活動的最早開始時間，顯然,eei= vej,。,數(shù),據(jù),結(jié),構(gòu),3,）事件,Vk,的最遲開始時間,vlk,vlk=minvlp-dut,?,T,必須在拓撲逆序前提下進行,(4),活動,a,的最遲開始時間,el,eli=vlk-dut,(5),只要某活動,a,i,有,eei=eli,的關(guān)系，我們就稱,a,i,為關(guān)鍵活動。關(guān)鍵路徑上各條邊所對應(yīng)的活動,都是關(guān)鍵活動。,數(shù),據(jù),結(jié),構(gòu),V2,V1,V3,V5,V4,V6,V1,V3,V4,V6,頂點,ve vl,活動,e l l-e,v1,v2,v3,v4,v5,v6,a

3、1,a2,a3,a4,a5,a6,a7,a8,0,0,3,4,2,6,6,8,2,6,7,8,0,0,3,3,2,2,6,6,1,1,0,4,4,2,5,6,7,0,1,1,0,3,0,1,數(shù),據(jù),結(jié),構(gòu),V2,V1,V3,V5,V4,V6,v6,v4,v5,v2,v3,v1,T,數(shù),據(jù),結(jié),構(gòu),T,T,v4,v5,S,v4,v2,v3,v1,T,S,T,v6,S,v6,v5,v4,v2,v3,v1,T,v3,v2,S,v3,v1,v1,T,v3,v2,v1,S,v4,v5,v2,S,v2,v3,v1,v6,v5,v5,v4,v2,v3,v1,數(shù),據(jù),結(jié),構(gòu),7,7,最短路徑,如果從圖中某頂點

4、出發(fā)（此點稱為源點），經(jīng)圖的,邊到達另一頂點（稱為終點）的路徑不止一條，如,何找到一條路徑使沿此路徑上各邊的權(quán)值之和為最,小。,7,7,1,從源點到其余頂點的最短路徑,?,迪杰斯特拉算法（,P190,）,用集合,S,記住已找到從,v,出發(fā)找到最短路徑,的終點的集合，一開始,S,中只包括頂點,v,，,用,T,記住剩下的頂點。,數(shù),據(jù),結(jié),構(gòu),?,若圖中有邊,v,v,j,則,v,j,的距離為此邊,的權(quán)值，否則,v,j,的距離值為一個很大的數(shù)，,?,每次從,T,的頂點中選一個其距離值最小的,Vm,加入到，,S,中。每往,S,加入一個頂點,Vm,，就要對,T,的各個頂,點,的距離值進行一次修正。若加進

5、,Vm,做中間頂點,使從,v,到,V,j,的最短路徑比不加,Vm,的路徑為短,則,要修改,Vj,的距離值。修改后再選距離最小的頂點,加入到,S,中。,?,如此進行下去，直到圖中所有頂點都包括在,S,中，,或再也沒有可加入到,S,中的頂點存在為止。,數(shù),據(jù),結(jié),構(gòu),V0,V5,V4,V2,V1,V3,20,30,終,點,i=1,i=2,i=3,i=4,i=,5,v,1,?,?,?,?,?,v,2,10,(v0,v2),v,3,?,60,(v0,v2,v3),50,(v0,v4,v3),v,4,30,(v0,v4),30,(v1,v4),v,5,100,(v0,v5),100,(v0,v5),90

6、,(v0,v4,v5),60,(v0,v4,v3,v5),v,j,v2,v4,v3,v5,S,v0,v2,v0,v2,v4,v0,v2,v3,v4,v0,v2,v3,v4,v5,數(shù),據(jù),結(jié),構(gòu),v0,v1,v2,v3,v4,v5,v1,v2,T,T,v3,v4,T,T,v5,T,T,v0,v1,v2,v3,v4,v5,v1,v2,T,T,v3,T,T,T,v4,T,T,v5,T,T,選,中,V2,綠,色,為,被,復(fù),制,的,內(nèi),容,Pv2=v0,v2,，,Pv3=Pv2+v3,，,Pv4=v0,v4,，,Pv5=v0,v5,（,1,）,（,2,）,紅色字體,表示復(fù)制,綠色部分,數(shù),據(jù),結(jié),構(gòu),

7、選,中,V4,v0,v1,v2,v3,v4,v5,v1,v2,T,T,v3,T,T,T,v4,T,T,v5,T,T,v0,v1,v2,v3,v4,v5,v1,v2,T,T,v3,T,T,T,v4,T,T,v5,T,T,T,Pv2=v0,v2,，,Pv3=Pv4+v3,，,Pv4=v0,v4,，,Pv5=Pv4+v5,Pv2=v0,v2,，,Pv3=Pv2+v3,，,Pv4=v0,v4,，,Pv5=v0,v5,（,2,）,（,3,）,數(shù),據(jù),結(jié),構(gòu),選,中,V3,v0,v1,v2,v3,v4,v5,v1,v2,T,T,v3,T,T,T,v4,T,T,v5,T,T,T,T,v0,v1,v2,v3,

8、v4,v5,v1,v2,T,T,v3,T,T,T,v4,T,T,v5,T,T,T,Pv2=v0,v2,，,Pv3=Pv4+v3,，,Pv4=v0,v4,，,Pv5=Pv4+v5,Pv2=v0,v2,，,Pv3=Pv4+v3,，,Pv4=v0,v4,，,Pv5=Pv3+v5,（,3,）,（,4,）,數(shù),據(jù),結(jié),構(gòu),v0,v1,v2,v3,v4,v5,v1,v2,T,T,v3,T,T,T,v4,T,T,v5,T,T,T,T,從上圖看到，,Pvv,為,T,，表示找到從源點,V0,到頂點,V,的最短路徑，,Pv2=v0,v2,，,Pv4=v0,v4,Pv3=Pv2+v3=v0,v2,v3,Pv5= P

9、v3+v5=v0,v2,v3,Pv2=v0,v2,，,Pv3=Pv4+v3,，,Pv4=v0,v4,，,Pv5=Pv3+v5,（,4,）,數(shù),據(jù),結(jié),構(gòu),7,7,2,從每對頂點間的最短路徑,?,弗洛伊德算法（,P192,）,?,如果從頂點,vi,到頂點,vj,有弧，則從頂點,vi,到頂,點,vj,存在一條長度為,Costij,的路徑，該路徑,不一定是最短路徑，尚需進行,n,次試探。,?,首先考慮路徑（,vi,，,v0,，,vj,）是否存在（即判,斷弧（,vi,，,v0,）和（,v0,，,vj,）是否存在）。如,果存在，則比較（,vi,，,v0,，,vj,）和（,vi,，,vj,）的,路徑長度，

10、然后取長度較短者為頂點,vi,到頂點,vj,的中間頂點的序號不大于,0,的最短路徑。,數(shù),據(jù),結(jié),構(gòu),?,假如在路徑上再增加一個頂點,v1,，也如果,（,vi,，,，,v1,）和（,v1,，,，,vj,）分別是,當(dāng)前找到的中間頂點的序號不大于,0,的最,短路徑，那么（,vi,，,，,v1,，,，,vj,）,就有可能是從,vi,到頂點,vj,的中間頂點的序,號不大于,l,的最短路徑。,數(shù),據(jù),結(jié),構(gòu),將它和已經(jīng)得到的從,vi,到頂點,vj,的中間頂點序,號不大于,0,的最短路徑相比較，從中選出中,間頂點的序號不大于,1,的最短路徑之后，再,增加一個頂點,v2,，繼續(xù)進行試探。依次類推,長度較短者便是從頂點,vi,到頂點,vj,的中間序號,不大于,k,的最短路徑。,經(jīng)過,n,次比較后，最后求得的必是從頂點,vi,到,頂點,vj,的最短路徑。,數(shù),據(jù),結(jié),構(gòu),v0,v1,v2,6,4,3,11,2,a,b,c,頂點間經(jīng)過,頂點的序號,?,-1,不存在,頂點間經(jīng)過,頂點的序號,?,0,既,v0,頂點間經(jīng)過頂,點的序號,?,1,既,v0,v1,頂點間經(jīng)過頂點,的序號,?,2,，