數(shù)據(jù)結(jié)構(gòu)課件-第七章圖5最短路徑

學習目標①

掌握圖的基本概念，包括圖、有向圖、無向圖、完全圖、子圖連通圖、度、入度、初度、簡單回路和環(huán)等基本概念的定義。②

重點掌握圖的各種

結(jié)構(gòu)、包括鄰接矩陣和鄰接表等③重點掌握圖的基本元素、包括創(chuàng)建圖、輸出圖、深度優(yōu)先遍歷、廣度優(yōu)先遍歷算法等④掌握圖的其他運算、包括最小生成樹、最短路徑、拓撲排序和關(guān)鍵路徑等算法⑤

靈活運

圖這種數(shù)據(jù)結(jié)構(gòu)解決一些綜合應用

。問題描述：V5V0V4V3V2V1在圖中，從一個頂點到另一個頂點間可能存在多條路徑，而每條路徑上經(jīng)過的邊數(shù)并不一定相同。比如V0到V5存在3條路徑V0->V5V0->V4->V5V0->V2->V3->V5最短路徑為V0->V5V4V530100V060101020V3V2V1

550問題描述：如果上述的圖的每條邊附上權(quán)值的話，則路徑長度為路徑上各邊的權(quán)值的總和，兩個頂點間路徑長度最短的那條路徑稱為兩個頂點間的最短路徑，則V0到V5間的3條路徑的長度分別為V0->V5

（100）V0->V4->V5

（30+60=90）V0->V2->V3->V5

（10+50+10=70）最短路徑為V0->V2->V3->V5問題：如何求一個頂點到其他頂點的最短路徑？從某個源點到其余各頂點的最短路徑算法主要思想：依最短路徑的長度遞增的次序求得各條路徑Step1：求出從源點到某個頂點v1的最短路徑，這條路徑只含一條弧，并且這條弧的權(quán)值最小。Step2：求出下一條次短路徑，這條路徑只可能有兩種情況：或者是直接從源點到該點(只含一條弧)；

或者是從源點經(jīng)過頂點v1，再到達該頂點v2(由兩條弧組成)。Step3：求再下一條次短路徑，它可能有三種情況：或者是直接從源點到該點

(只含一條弧)；或者是從源點經(jīng)過頂點v1，再到達該頂點(由兩條弧組成)；或者是從源點經(jīng)過頂點v2，再到達該頂點。Step4：依次求其他最短路徑，它或者是直接從源點到該點(只含一條弧)；或者是從源點經(jīng)過已求得最短路徑的頂點，再到達該頂點。Dijkstra算法——Single

Source/All

Destinations設(shè)置輔助數(shù)組D，其中每個分量 表示當前所求得的從源點到其余各頂點

k的最短路徑。一般情況下，D

[k]=<源點到頂點k的弧上的權(quán)值>或者=<源點到其它頂點的路徑長度>+<其它頂點到頂點k

的弧上的權(quán)值>。1）在所有從源點出發(fā)的弧中選取一條權(quán)值最小的弧，即為第一條最短路徑。V0和k之間存在弧V0和k之間不存在弧INFINITYD[k

]

G.arcs

[v0][k

]2）修改其它各頂點的D

[k]值。假設(shè)求得最短路徑的頂點為u，若Dist[u]+G.arcs[u][k]<Dist[k]則將D

[k]改為D

[u]+G.arcs[u][k]。Dijkstra算法描述1、初始化：S

←{v0};dist[j]

←

Edge[0][j],

j

, ,

…,

n-1;//n為圖中頂點個數(shù)2、求出最短路徑的長度：dist[k]

←

min{

dist[i]

},

i

V-

S;S←

SU

{

k

};3、修改：dist[i]

←

min{

dist[i],

dist[k]

+

Edge[k][i]

},對于每一個i

V-S

;4、判斷：若S=V,則算法結(jié)束，否則轉(zhuǎn)2。Dijkstra算法演示V4V530100

60V0V1101020V25V3500201234∞∞10∞30100∞∞5∞∞∞∞∞∞50∞∞∞∞∞∞∞10∞∞∞20∞60∞∞∞∞∞∞5點求解過程12345V1∞∞∞∞∞V2

10(V0,V2)V3∞60

50(V 0,V2,V3

)(V0,V4,V3)V430V0,V430(V0,V4)V5100(V0,V5)100(V0,V5)V

jV2V490

60(V0,V4,V5

)(V0,V4,V3,V5)V3

V5SV0,V2V0,V2,V4V0,V2,V4,

V3V0,V2,V4,

V3,V5/*Dijkstra算法*/void

Dijkstra(Graph

&g){int

total=0;int

adjvex[6];//計數(shù)變量，計算共選擇節(jié)點多少個//保存依次被選中的節(jié)點edge

lo

thcost[6];

//初始值為矩陣的第一行char

path[6][10]={"0","","","","",""};

//以初始節(jié)點開始計算最短路徑

(路徑)for(int

i=1;i<6;i++){

lo

thcost[i].cost=g.cost[0][i];//初始化為M，最短路徑長度為矩陣的第一行權(quán)值if(g.cost[0][i]!=M){lo

thcost[i].adjvex=0;//有數(shù)據(jù)則adjvex置為cout<<"初始存在路徑的是"<<lo

thcost[i].adjvex<<"----"<<i<<endl;

}}int

min;

//保存最小權(quán)值int

minvex;

//保存最小權(quán)值邊的另一頂點int

selected[6]={0};

//次變量是作為控制已輸出的節(jié)點不再參與的判斷參數(shù)//此時adjvex[1]為，存放依次選出cout<<endl<<"開始選擇頂點："<<endl;for(int

num=1;num<=5;num++)

//要選擇的次數(shù),除掉起點{

min=M;for(i=1;i<=5;i++)if(min>lo

thcost[i].cost&&!selected[i])lo thcost[i

.

;//第一次查找為即第一行中最小的值minvex=i;//此時i=2

}adjvex[++total]=minvex;的頂點if(min!=M){

cout<<"第"<<num<<"

次被選擇的頂點是:"

<<minvex<<"

. "

<<"對應的邊上的權(quán)值是"<<min<<endl;

}selected[minvex]=1;

//已參與的節(jié)點就置為1for(i=0;i<6;i++)

//更新各個路徑的

取值if(!selected[i]

&&

lo

thcost[i].cost>min+g.cost[minvex][i]

&&

min+g.cost[minvex][i]<M)//3項都要滿足{

lo

thcost[i].cost=min+g.cost[minvex][i];lo

thcost[i].adjvex=minvex}thcost[i].adjvex;for(i=1;i<=5;i++)cout<<"

"<<locout<<endl<<endl;int

ead

vex,sad

vex;char

ep[2];for(i=1;i<=total;i++){

eadjvex=adjvex[i];sadjvex=lo

thcost[eadjvex].adjvex;ep[0]='0'+eadjvex;

ep[1]='\

'char

tmp[10];strcpy(tmp,path[sadjvex]);strcpy(path[eadjvex],strcat(tmp,ep));cout<<"0

到頂點"<<eadjvex

<<"

的最短路徑經(jīng)歷的節(jié)點依次是："<<path[eadjvex]<<"

長度是："<<lo

thcost[eadjvex].cost<<endl;}

}每一對頂點之間的最短路徑問題的提法：已知一個各邊權(quán)值均大于0的帶權(quán)有向圖，對每一對頂點vi

vj，要求求vi

與vj之間的最短路徑和最短路徑長度。解決辦法:

算法，其主要思想是從

vi到

vj的所有可能存在的路徑中，選出一條長度最短的路徑。算法將有向圖G=(V,E)，用鄰接矩陣cost存放另外設(shè)置一個二維數(shù)組A，存放當前頂點之間的最短路徑定義A[i][j]表示當前頂點vi到頂點vj的最短路徑長度算法的思想遞推產(chǎn)生矩陣序列A0,A1,…,Ak,…,An-1其中Ak[i][j]表示從vi到vj的路徑上包含的頂點的

不大于k若<vi,vj>存在，則存在路徑{vi,vj}//路徑中不含其它頂點若<vi,v0>,<v0,vj>存在，則存在路徑{vi,v0,vj}//路徑中所含頂點序號不大于0若{vi,…,v1},{v1,…,vj}存在，則存在一條路徑{vi,…,v1,…vj}//

路徑中所含頂點序號不大于1

…若{vi,…,vk},{vk,…,vj}存在，則存在一條路徑{vi,…,vk,…,vj}//

路徑中所含頂點序號不大于k

…依次類推，則vi至vj的最短路徑應是上述這些路徑中，路徑長度最小者。算法演示Step1:初始狀態(tài)，A-

=A-1

=路徑：ABACBABCCAAB640

4

113

02311CABACBABCCACABcost

=Step2:加入A點考慮，經(jīng)過A的路徑有CAB和BAC，則修改CB距離從

變?yōu)?，而BAC的距離長于BC，則BC距離不改。6

0

23

7

0A0

=路徑：0

4

116

0

23

0算法演示AB64Step3:加入B點考慮，經(jīng)過B的路徑有ABC，路徑為6<AC,修改AC的距離從11到6231166

0

23

7

0A1

=路徑：ABABCBABCCACABCStep4:加入C點考慮，經(jīng)過C的路徑有BCA，路徑為5<BA,修改BA的距離從6到5cost

=A2

=路徑：0

4

116

0

23

00

4

653

7

0BAB

ABCBCACCA

CAB結(jié)論：經(jīng)過4次迭代后，矩陣A中存放的是各個頂點間的最短路徑/*Floyd算法*/void

Floyd(Graph

&G){ int

D[10][10],P[10][10][10];//P[v][w][k]為TRUE，則從v到w的最短路徑中含有k節(jié)點//D[v][w]從v到w的最短路徑的長度G.vexnum;

v++)for

(w

=

0;

w

<

G.vexnum;

w++){D[v][w]

=

G.cost[v][w];for

(k

=

0;

k

<

G.vexnum;

k++)P[v][w][k]

=

FALSE;if

(D[v][w]

<

M)P[v][w][v]

=

P[v][w][w]

=

TRUE;}for

(k

=

0;

k

<

G.vexnum;

k++)for

(v

=

0;

v

<

G.vexnum;

v++)for

(w

=

0;

w

<

G.vexnum;

w++)if

(D[v][k]

+

D[k][w]

<

D[v][w]){D[v][w]

=

D[v][k]

+

D[k][w];fo