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

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

S中頂點(diǎn)：從V0到此頂點(diǎn)的最短路徑長(zhǎng)度

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

初始化：S←{v0};

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

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

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

V-S;S←S

U{k

};2、

修改：

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

對(duì)于每一個(gè)i

V-S;3、

判斷：若S=V,則算法結(jié)束，否則轉(zhuǎn)1。計(jì)算從單個(gè)頂點(diǎn)到其它各個(gè)頂點(diǎn)的最短路徑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; //頂點(diǎn)v加入頂點(diǎn)集合

//選擇當(dāng)前不在集合S中具有最短路徑的頂點(diǎn)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;

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

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

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