數(shù)據(jù)結(jié)構(gòu)第七講(4)最短路徑

7.6關(guān)鍵路徑問題提出把工程計劃表示為有向圖，用頂點表示事件，弧表示活動；每個事件表示在它之前的活動已完成，在它之后的活動可以開始例設(shè)一個工程有11項活動，9個事件事件V1——表示整個工程開始事件V9——表示整個工程結(jié)束問題：（1）完成整項工程至少需要多少時間？（2）哪些活動是影響工程進(jìn)度的關(guān)鍵？987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4定義AOE網(wǎng)(ActivityOnEdge)——也叫邊表示活動的網(wǎng)。AOE網(wǎng)是一個帶權(quán)的有向無環(huán)圖，其中頂點表示事件，弧表示活動，權(quán)表示活動持續(xù)時間路徑長度——路徑上各活動持續(xù)時間之和關(guān)鍵路徑——路徑長度最長的路徑叫~Ve(j)——表示事件Vj的最早發(fā)生時間Vl(j)——表示事件Vj的最遲發(fā)生時間e(i)——表示活動ai的最早開始時間l(i)——表示活動ai的最遲開始時間l(i)-e(i)——表示完成活動ai的時間余量關(guān)鍵活動——關(guān)鍵路徑上的活動叫~，即l(i)=e(i)的活動問題分析如何找e(i)=l(i)的關(guān)鍵活動？設(shè)活動ai用弧<j,k>表示，其持續(xù)時間記為：dut(<j,k>)則有：（1）e(i)=Ve(j)（2）l(i)=Vl(k)-dut(<j,k>)jkai如何求Ve(j)和Vl(j)？(1)從Ve(1)=0開始向前遞推(2)從Vl(n)=Ve(n)開始向后遞推求關(guān)鍵路徑步驟求Ve(i)求Vl(j)求e(i)求l(i)計算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9頂點VeVl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活動ell-e000022660462583770770710316160141400337.7最短路徑問題提出用帶權(quán)的有向圖表示一個交通運(yùn)輸網(wǎng)，圖中：頂點——表示城市邊——表示城市間的交通聯(lián)系權(quán)——表示此線路的長度或沿此線路運(yùn)輸所花的時間或費(fèi)用等問題：從某頂點出發(fā)，沿圖的邊到達(dá)另一頂點所經(jīng)過的路徑中，各邊上權(quán)值之和最小的一條路徑——最短路徑從某個源點到其余各頂點的最短路徑51643208562301371732913長度最短路徑<V0,V1><V0,V2><V0,V2,V3><V0,V2,V3,V4><V0,V2,V3,V4,V5><V0,V1,V6>813192120迪杰斯特拉(Dijkstra)算法思想按路徑長度遞增次序產(chǎn)生最短路徑算法：把V分成兩組：（1）S：已求出最短路徑的頂點的集合（2）V-S=T：尚未確定最短路徑的頂點集合將T中頂點按最短路徑遞增的次序加入到S中，保證：（1）從源點V0到S中各頂點的最短路徑長度都不大于從V0到T中任何頂點的最短路徑長度（2）每個頂點對應(yīng)一個距離值

S中頂點：從V0到此頂點的最短路徑長度

T中頂點：從V0到此頂點的只包括S中頂點作中間頂點的最短路徑長度依據(jù)：可以證明V0到T中頂點Vk的最短路徑，或是從V0到Vk的直接路徑的權(quán)值；或是從V0經(jīng)S中頂點到Vk的路徑權(quán)值之和（反證法可證）Dijkstra算法可描述如下：

初始化：S←{v0};

dist[j]←Edge[0][j],j=1,2,…,n-1;

//n為圖中頂點個數(shù)1、求出最短路徑的長度：

dist[k]←min{dist[i]},i

V-S;S←S

U{k

};2、

修改：

dist[i]←min{dist[i],dist[k]+Edge[k][i]},

對于每一個i

V-S;3、

判斷：若S=V,則算法結(jié)束，否則轉(zhuǎn)1。計算從單個頂點到其它各個頂點的最短路徑ShortestPath(

constint

n,

constint

v){

for(

inti=0;

i<n;

i++)

{

dist[i]=Edge[v][i];

//dist數(shù)組初始化

S[i]=0;

if(i!=v

&&

dist[i]<MAXINT)path[i]=v;

else

path[i]=-1; //path數(shù)組初始化

}

S[v]=1;

dist[v]=0; //頂點v加入頂點集合

//選擇當(dāng)前不在集合S中具有最短路徑的頂點u

for(i=0;

i<n-1;

i++){

int

min=MAXINT;

int

u=v;

for(

int

j=0;

j<n;

j++)

if(!S[j]&&

dist[j]<min)

{

u=j;

min=

dist[j];

}

S[u]=1;

//將頂點u加入集合S

for(

int

w=0;

w<n;

w++)//修改

if(!S[w]&&

Edge[u][w]<MAXINT&&

dist[u]+Edge[u][w]<

dist[w]){

dist[w]=

dist[u]+Edge[u][w];

path[w]=u;

}

}}

13<V0,V1>8<V0,V2>30<V0,V4>32<V0,V6>V2:8<V0,V2>13<V0,V1>-------13<V0,V2,V3>30<V0,V4>32<V0,V6>V1:13<V0,V1>--------------13<V0,V2,V3>30<V0,V4>22<V0,V1,V5>20<V0,V1,V6>V3:13<V0,V2,V3>---------------------19<V0,V2,V3,V4>22<V0,V1,V5>20<V0,V1,V6>V4:19<V0,V2,V3,V4>終點從V0到各終點的最短路徑及其長度V1V2V3V4V5V6Vj--------------------------------21<V0,V2,V3,V4,V5>20<V0,V1,V6>V6:20<V0,V1,V6>516432085623013717329每一對頂點之間的最短路徑方法一：每次以一個頂點為源點，重復(fù)執(zhí)行Dijkstra算法n次——T(n)=O(n3)方法二：弗洛伊德(Floyd)算法算法思想：逐個頂點試探法求最短路徑步驟初始時設(shè)置一個n階方陣，令其對角線元素為0，若存在弧<Vi,Vj>，則對應(yīng)元素為權(quán)值；否則為逐步試著在原直接路徑中增加中間頂點，若加入中間點后路徑變短，則修改之；否則，維持原值所有頂點試探完畢，算法結(jié)束對于每一對頂點u和v，看看是否存在一個頂點w使得從u到w再到v比己知的路徑更短。如果是更新它。不可思議的是，只要按排適當(dāng)，就能得到結(jié)果。//dist(i,j)為從節(jié)點i到節(jié)點j的最短距離Fori←1tondoForj←1tondodist(i,j)=weight(i,j)Fork←1tondo//k為“中間節(jié)點”

if(dist(i,k)+dist(k,j)<dist(i,j))then//是否是更短的路徑？

dist(i,j)=dist(i,k)+dist(k,j)例ACB264311041160230初始：路徑：ABACBABCCA046602370加入V2：路徑：ABA