最短路徑問(wèn)題課件

20最短路徑最短路徑問(wèn)題關(guān)鍵路徑復(fù)習(xí)從某個(gè)源點(diǎn)到其余各點(diǎn)的最短路徑每一對(duì)頂點(diǎn)之間的最短路徑小結(jié)和作業(yè)20最短路徑關(guān)鍵路徑1、求出拓?fù)渑判蛐蛄?、ve(0)=0ve(j)=max(ve(i)+dut(i,j))

<i,j>∈T,T是以j為頭的弧的集合3、求出逆拓?fù)渑判蛐蛄?、vl(n-1)=ve(n–1)v(i)=min(vl(j)-dut(i,j))

<i,j>∈T,T是以j為頭的弧的集合20最短路徑關(guān)鍵路徑5、對(duì)每個(gè)活動(dòng)ai，對(duì)應(yīng)的弧是<j,k>

e(i)=ve(j)l(i)=vl(k)–dut(j,k)

6、對(duì)每個(gè)活動(dòng)ai

，如果，e(i)=l(i)，輸出ai，ai是關(guān)鍵活動(dòng)20最短路徑關(guān)鍵路徑A練習(xí)：求下圖各活動(dòng)弧ai的e(ai)和l(ai)，個(gè)事件vj的ve(vj)和vl(vj)，列出各關(guān)鍵路徑。BCDEFGHWXa1=1a2=6a3=3a4=4a5=2a6=7a7=5a8=10a9=6a10=11a11=8a12=21a13=16a14=9a15=17a16=13a17=1220最短路徑關(guān)鍵路徑算法StatusToplogicalOrder(ALGraghG,Stack&T,SqList&ve){ InitStack(S);InitStack(T);count=0;ve[0..G.vexnum-1]=0;FindInDegree(G,indegree); for(i=0;i<G.vexnum;i++){if(!indegree[i])push(S,i);}

while(!EmptyStack(S)){

…………}//while if(count<G.vexnum)returnERROR; elsereturnOK;}20最短路徑關(guān)鍵路徑算法while(!EmptyStack(S)){Pop(S,v);Push(T,v);++count;for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)){ if(--indegree(w)==0)Push(S,w);//入度-1為0，則入棧

if(ve[v]+<v,w>>ve[w])ve[w]=ve[v]+<v,w>//計(jì)算ve}//for}//while

20最短路徑關(guān)鍵路徑算法StatusCriticalPath(ALGraghG){//逆鄰接表

if(!ToplogicalOrder(G,T,ve))returnERROR;

vl[0..G.vexnum-1]=ve[0..G.vexnum-1];//用ve初始化vl

while(!stackEmpty(T)){

pop(T,v);

//計(jì)算vlfor(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)){ if(vl[v]-<w,v><vl[w])vl[w]=vl[v]-<w,v>;

}//for

}//while

…………}//endofCriticalPath20最短路徑關(guān)鍵路徑算法

for(j=0;j<G.vexnum;++j)

for(p=G.vertices[j].firstarc;p;p=p->nextarc){

k=p->adjvex;dut=*(p->info);

ee=ve[k];el=vl[j]-dut;//活動(dòng)的時(shí)間

tag=(ee=el)?’*’:’’;

printf(j,k,dut,ee,el,tag);

}//endoffor(p)20最短路徑關(guān)鍵路徑算法分析1.求關(guān)鍵路徑的總的時(shí)間復(fù)雜度：O(n+e)2.AOE-網(wǎng)求出的路徑可能大于一條。這種情況下只有同時(shí)提高所有關(guān)鍵路徑上的活動(dòng)的速度，才能使整個(gè)工期縮短。20最短路徑單源點(diǎn)的最短路徑V01001010550V1V2V5V460V32030給定帶權(quán)有向圖G和V0，求從V0到其余各頂點(diǎn)的最短路徑。20最短路徑Dijkstra算法按照路徑長(zhǎng)度遞增的次序產(chǎn)生最短路徑源點(diǎn)v1…v220最短路徑終點(diǎn)一定是V0的鄰接點(diǎn)Vj，邊一定是<V0,Vj>，它在V0的所有鄰接邊中最短。該路徑是V0Vj1、長(zhǎng)度最短的路徑V01001010550V1V2V5V460V32030Dijkstra算法20最短路徑如果路徑V0Vj

不是最短路徑，則一定有另外一條路徑，V0W…U,它比V0Vj短。但是，因?yàn)閃是V0的鄰接點(diǎn)，所以，邊<V0,W>一定比邊<V0,Vj>長(zhǎng)。所以，不存在比V0Vj更短的路徑。不失一般性，假設(shè)j=1Dijkstra算法20最短路徑它只可能有兩種情況:

1）直接從源點(diǎn)到該點(diǎn),V0X2）從源點(diǎn)經(jīng)過(guò)頂點(diǎn)v1，再到達(dá)該頂點(diǎn),V0V1X假設(shè)存在另外一個(gè)路徑，V0WX，它比上面的路徑更短。如果W≠V1，則V0W比V0WX更短，所以，要選取W，符合形式一如果W=V1，則符合形式二Dijkstra算法2、下一條路徑長(zhǎng)度次短的最短路徑的特點(diǎn):20最短路徑3、用S表示已經(jīng)選取的頂點(diǎn)集合

S={V0,V1,V2,…Vj}下次要選取的頂點(diǎn)X，從V0到X的路徑中經(jīng)過(guò)的頂點(diǎn)一定都在S中。假設(shè)存在路徑V0→→W→X，WS，該路徑最短。因?yàn)槁窂絍0→→W→X比路徑V0→→W長(zhǎng)，所以會(huì)選擇W，而V0到W的路徑中的頂點(diǎn)都在S中。Dijkstra算法20最短路徑V01001010550V1V2V5V460V32030S={V0}S={V0,V2}S={V0,V2,V4}S={V0,V2,V4,V3}S={V0,V2,V4,V3,V5}V2V5V4V3Dijkstra算法20最短路徑為了減少計(jì)算量設(shè)置輔助數(shù)組D，其中每個(gè)分量D[k]

表示當(dāng)前所求得的從源點(diǎn)到頂點(diǎn)k

的最短路徑。初始時(shí)

D[k]=<源點(diǎn)到頂點(diǎn)k的弧上的權(quán)值>當(dāng)S=S∪{Vj}D[K]=min(D[k],D[Vj]+<Vj,K>)Dijkstra算法20最短路徑abcdefg15210765910444終點(diǎn)bcdefgD路徑15ab2ac10ad2

9ace6acf6

169

10

1414

acfgadgDijkstra算法20最短路徑如何保存V0到V的路徑？1、保存V0到V的路徑上的頂點(diǎn)（即：不保存邊和頂點(diǎn)之間的順序）2、存儲(chǔ)結(jié)構(gòu)：n×n的矩陣pDijkstra算法3、矩陣的第V行表示V0到V的路徑上頂點(diǎn)如果頂點(diǎn)W在路徑上，則p[v][w]=TRUE否則，p[v][w]=FALSE20最短路徑初始：如果V與頂點(diǎn)V0鄰接，則p[v][V0]=TRUE，其它數(shù)矩陣元素的值都是FALSE。當(dāng)從V0到V的路徑是經(jīng)過(guò)V0到W的路徑，然后，通過(guò)邊<W,V>到達(dá)V，則p[v]=p[w]，p[v][v]=TRUEDijkstra算法20最短路徑Dijkstra算法V01001010550V1V2V5V460V32030F

FFFFFV0V1V2V3V4V5V0V1V2V3V4V5FFFFFF

TFTFFF

FFFFFF

TFFFTF

TFFFFT選取V2后，V0到V3的路徑經(jīng)過(guò)V2P[V3]=P[V2]P[V3][V3]=TRUE

TFTFFF

TFT

TFF20最短路徑Dijkstra算法描述1）在所有從源點(diǎn)出發(fā)的弧中選取一條權(quán)值最小的弧，即為第一條最短路徑。2）修改其它各頂點(diǎn)的D[k]值。假設(shè)求得最短路徑的頂點(diǎn)為u，若D[u]+G.arcs[u][k]<D[k]則將D[k]=D[u]+G.arcs[u][k]V0和k之間存在弧V0和k之間不存在弧Dijkstra算法20最短路徑Dijkstra算法實(shí)現(xiàn)圖：帶權(quán)的鄰接矩陣

路徑：矩陣距離：數(shù)組DS中的集合：數(shù)組final[]，如果final[v]=TRUE，則v在S中20最短路徑voidShortestPath_DIJ(MGraphG,intv0,PathMatrix&P, ShortestPathTable&D){

for(v=0;v<G.vexnum;++v){

final[v]=FALSE;//S中的頂點(diǎn)

D[v]=G.arcs[v0][v];//V0到v的路徑的長(zhǎng)度

for(w=0;w<G.vexnum;++w)

p[v][w]=FALSE;

if(D[v]<INFINITY){//V0的鄰接點(diǎn)

p[v][v0]=TRUE;

p[v][v]=TRUE; }//if }//for

final[v0]=TRUE;

…………}Dijkstra算法實(shí)現(xiàn)20最短路徑voidShortestPath_DIJ(MGraphG,intv0,PathMatrix&P, ShortestPathTable&D){

//主循環(huán)，每次求得v0到某個(gè)頂點(diǎn)v的最短路徑，

//并將v加到S集中

for(i=1;i<G.vexnum;++i){

min=INFINITY;//找余下頂點(diǎn)中的最短路徑

for(w=0;w<G.vexnum;++w){ if(!final[w])

if(D[w]<min){v=w;min=D[w];}

final[v]=TRUE;//v入選，即v0到v的路徑最短

…………}}Dijkstra算法實(shí)現(xiàn)20最短路徑voidShortestPath_DIJ(MGraphG,intv0,PathMatrix&P, ShortestPathTable&D){

for(w=0;w<G.vexnum;++w) {

if(!final[w]&&(min+G.arcs[v][w]<D[w])){

D[w]=min+G.arcs[v][w];//修改距離

p[w]=p[v];//修改路徑

p[w][w]=TRUE; }//endofif }//endoffor}//voidDijkstra算法實(shí)現(xiàn)20最短路徑課堂練習(xí)123456787810152030601015163366求出從頂點(diǎn)1到其它定點(diǎn)的最短路徑。要求寫出final、D、和p的變化過(guò)程。20最短路徑Dijkstra算法討論2、權(quán)值要為正數(shù)，否則，得不到正確結(jié)果1、算法的總的時(shí)間復(fù)雜度：O(n2)3、當(dāng)權(quán)值出現(xiàn)負(fù)數(shù)時(shí)，要使用Bellman-Ford算法20最短路徑Dijkstra算法討論都是從一個(gè)頂點(diǎn)開始都有一個(gè)距離數(shù)組D都有一個(gè)頂點(diǎn)是否已經(jīng)被選取的標(biāo)志4、和Prim算法有相似和不同的地方20最短路徑abcdegf195141827168213127abegf14d8c351621Prim算法產(chǎn)生的最小生成樹Dijkstra算法討論20最短路徑abcdegf195141827168213127abegf14d8c51821Dijkstra算法產(chǎn)生的支撐樹19Dijkstra算法討論20最短路徑每一對(duì)頂點(diǎn)之間的最短路徑v0v2v1326411cab問(wèn)題：給定一個(gè)圖G，求出G中任意兩個(gè)頂點(diǎn)之間的最短路徑（距離和經(jīng)過(guò)的頂點(diǎn)）解決方法：對(duì)圖中的每個(gè)結(jié)點(diǎn)V，以V為源點(diǎn)，調(diào)用Dijkstra算法時(shí)間復(fù)雜度為O(n3)20最短路徑首先假設(shè)頂點(diǎn)vi和vj之間的最短路徑是通過(guò)連接vi到j(luò)的弧，然后不斷的調(diào)整它從vi

到vj的所有可能存在的路徑中，選出一條長(zhǎng)度最短的路徑弗洛伊德算法的基本思想是動(dòng)態(tài)規(guī)劃Floyd

算法20最短路徑考察從Vi到Vj且中間頂點(diǎn)屬于集合{V1,V2,...Vk}的所有路徑，設(shè)其中最短的一條路徑為P。Floyd

算法若Vk不是路徑P的中間節(jié)點(diǎn)，則P的所有中間頂點(diǎn)都屬于集合{V1,V2,..Vk-1};因此從Vi到Vj且中間頂點(diǎn)屬于集合{V1,V2,...Vk-1}的最短路徑也是從Vi到Vj且中間頂點(diǎn)屬于集合{V1,V2,...Vk}的最短路徑；20最短路徑Floyd

算法若Vk是P的中間節(jié)點(diǎn)，我們把P分解成P1={Vi,...Vk}和P2={Vk,..,Vj}，顯然P1是從Vi到Vk的一條最短路徑且滿足所有的中間頂點(diǎn)均屬于集合{V1,V2,..Vk-1};P2是從Vk到Vj的一條最短路徑且滿足所有的中間頂點(diǎn)均屬于集合{V1,V2,..Vk-1};20最短路徑Floyd

算法對(duì)任一對(duì)頂點(diǎn)Vi和Vj求Vi和Vj之間經(jīng)過(guò)中間頂點(diǎn)集合{V1}的最短路徑再求Vi和Vj之間經(jīng)過(guò)中間頂點(diǎn)集合{V1，V2}的最短路徑設(shè)P1是Vi到V2，且中間頂點(diǎn)集合是{V1}的最短路徑設(shè)P2是V2到Vj，且中間頂點(diǎn)集合是{V1}的最短路徑如果P1+P2<P(Vi,Vj)，則P1+P2是Vi到Vj的最短路徑，經(jīng)過(guò)的中間頂點(diǎn)是{V1,V2}20最短路徑Floyd

算法直到求出頂點(diǎn)Vi和Vj之間經(jīng)過(guò){V1,V2,…,Vn}的最短路徑20最短路徑Floyd

算法1.定義一個(gè)n階方陣D(-1)，表示初始時(shí)，任意兩個(gè)頂點(diǎn)(i,j)之間的距離

D(-1)[i][j]=G.arcs[i][j]

由D(k-1)生成新的矩陣D(k),表示任意連個(gè)頂點(diǎn)之間最短路徑的長(zhǎng)度，中間經(jīng)過(guò)的頂點(diǎn)的編號(hào)小于K。

D(k)=Min(D(k-1)[i][j],D(k-1)[i][k]+D(k-1)[k][j]2.fork=0ton-13.D(n)中存放的是任意兩個(gè)頂點(diǎn)之間的最短路徑20最短路徑0121200403∞121200D-1v0v2v1326411cab116200ab0caacbabc0P-1Floyd

算法演示20最短路徑121200v0v2v1326411cab0121200403∞116200ab0caacbabc0437cabD0P0Floyd

算法演示20最短路徑11121200v0v2v1326411cab0121200066200ab0caacbabc0437cab24abcD1P1Floyd

算法演示20最短路徑6121200v0v2v1326411cab012120006200ab0caacbabc0437cababc235bcaD2P2Floyd

算法演示20最短路徑采用鄰接矩陣存儲(chǔ)每對(duì)頂點(diǎn)之間的路徑長(zhǎng)度采用三維數(shù)組存儲(chǔ)每對(duì)頂點(diǎn)之間經(jīng)過(guò)的頂點(diǎn)Floyd

算法實(shí)現(xiàn)20最短路徑voidshortestPath_FLOYD(MGraphG,PathMatrix&P[], DistancMatrix&D){

for(v=0;v<G.vexnum;++v)//各對(duì)頂點(diǎn)初始已知路徑和距離

for(w=0;w<G.vexnum;++w){

D[v][w]=G.arcs[v][w];//D-1

for(u=0;u<G.vexnum;++u)P[v][w][u]=FALSE;

if(D[v][w]<INFINITY){//從v到w有直接路徑

P[v][w][v]=TRUE;//P-1

P[v][w][w]=TRUE;

}//if

}//for

…………

}Floyd

算法實(shí)現(xiàn)20最短路徑voidshortestPath_FLOYD(MGraphG,PathMatrix&P[], DistancMatrix&D){

…………

for(u=0;u<G.vexnum;++u)//中間結(jié)點(diǎn) for(v=0;v<G.vexnum;++v){

for(w=0;w<G.vexnum;++w)

if(D[v][u]+D[u][w]<D[v][w]){

//從v經(jīng)u到w的一條路徑更短

D[v][w]=D[v][u]+D[u][w];

for(i=0;i<G.vexnum;i++)