最短路徑問題課件

20最短路徑最短路徑問題關(guān)鍵路徑復(fù)習從某個源點到其余各點的最短路徑每一對頂點之間的最短路徑小結(jié)和作業(yè)20最短路徑關(guān)鍵路徑1、求出拓撲排序序列2、ve(0)=0ve(j)=max(ve(i)+dut(i,j))

<i,j>∈T,T是以j為頭的弧的集合3、求出逆拓撲排序序列4、vl(n-1)=ve(n–1)v(i)=min(vl(j)-dut(i,j))

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

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

6、對每個活動ai

，如果，e(i)=l(i)，輸出ai，ai是關(guān)鍵活動20最短路徑關(guān)鍵路徑A練習：求下圖各活動弧ai的e(ai)和l(ai)，個事件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>//計算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);

//計算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;//活動的時間

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

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

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

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

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

S={V0,V1,V2,…Vj}下次要選取的頂點X，從V0到X的路徑中經(jīng)過的頂點一定都在S中。假設(shè)存在路徑V0→→W→X，WS，該路徑最短。因為路徑V0→→W→X比路徑V0→→W長，所以會選擇W，而V0到W的路徑中的頂點都在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最短路徑為了減少計算量設(shè)置輔助數(shù)組D，其中每個分量D[k]

表示當前所求得的從源點到頂點k

的最短路徑。初始時

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

9ace6acf6

169

10

1414

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

FFFFFV0V1V2V3V4V5V0V1V2V3V4V5FFFFFF

TFTFFF

FFFFFF

TFFFTF

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

TFTFFF

TFT

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

D[v]=G.arcs[v0][v];//V0到v的路徑的長度

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

p[v][w]=FALSE;

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

p[v][v0]=TRUE;

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

final[v0]=TRUE;

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

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

//并將v加到S集中

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

min=INFINITY;//找余下頂點中的最短路徑

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

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

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

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

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

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

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

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

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

由D(k-1)生成新的矩陣D(k),表示任意連個頂點之間最短路徑的長度，中間經(jīng)過的頂點的編號小于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)中存放的是任意兩個頂點之間的最短路徑20最短路徑0121200403∞121200D-1v0v2v1326411cab116200ab0caacbabc0P-1Floyd

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

算法演示20最短路徑11121200v0v2v1326411cab0121200066200ab0caacbabc0437cab24abcD1P1Floyd

算法演示20最短路徑6121200v0v2v1326411cab012120006200ab0caacbabc0437cababc235bcaD2P2Floyd

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

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

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

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

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

…………

for(u=0;u<G.vexnum;++u)//中間結(jié)點 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++)