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

學(xué)習(xí)目標(biāo)①

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

重點(diǎn)掌握圖的各種

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

靈活運(yùn)

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

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

550問題描述：如果上述的圖的每條邊附上權(quán)值的話，則路徑長度為路徑上各邊的權(quán)值的總和，兩個(gè)頂點(diǎn)間路徑長度最短的那條路徑稱為兩個(gè)頂點(diǎ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問題：如何求一個(gè)頂點(diǎn)到其他頂點(diǎn)的最短路徑？從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑算法主要思想：依最短路徑的長度遞增的次序求得各條路徑Step1：求出從源點(diǎn)到某個(gè)頂點(diǎn)v1的最短路徑，這條路徑只含一條弧，并且這條弧的權(quán)值最小。Step2：求出下一條次短路徑，這條路徑只可能有兩種情況：或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)；

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

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

Source/All

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

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

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

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

]

G.arcs

[v0][k

]2）修改其它各頂點(diǎn)的D

[k]值。假設(shè)求得最短路徑的頂點(diǎn)為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為圖中頂點(diǎn)個(gè)數(shù)2、求出最短路徑的長度：dist[k]

←

min{

dist[i]

},

i

V-

S;S←

SU

{

k

};3、修改：dist[i]

←

min{

dist[i],

dist[k]

+

Edge[k][i]

},對于每一個(gè)i

V-S

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

60V0V1101020V25V3500201234∞∞10∞30100∞∞5∞∞∞∞∞∞50∞∞∞∞∞∞∞10∞∞∞20∞60∞∞∞∞∞∞5點(diǎn)求解過程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];//計(jì)數(shù)變量，計(jì)算共選擇節(jié)點(diǎn)多少個(gè)//保存依次被選中的節(jié)點(diǎn)edge

lo

thcost[6];

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

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

//以初始節(jié)點(diǎn)開始計(jì)算最短路徑

(路徑)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)值邊的另一頂點(diǎn)int

selected[6]={0};

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

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

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

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

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

.

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

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

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

次被選擇的頂點(diǎn)是:"

<<minvex<<"

. "

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

}selected[minvex]=1;

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

//更新各個(gè)路徑的

取值if(!selected[i]

&&

lo

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

&&

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

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

到頂點(diǎn)"<<eadjvex

<<"

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

長度是："<<lo

thcost[eadjvex].cost<<endl;}

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

vj，要求求vi

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

算法，其主要思想是從

vi到

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

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

路徑中所含頂點(diǎn)序號不大于1

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

路徑中所含頂點(diǎn)序號不大于k

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

=A-1

=路徑：ABACBABCCAAB640

4

113

02311CABACBABCCACABcost

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

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

0

23

7

0A0

=路徑：0

4

116

0

23

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

0

23

7

0A1

=路徑：ABABCBABCCACABCStep4:加入C點(diǎn)考慮，經(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中存放的是各個(gè)頂點(diǎn)間的最短路徑/*Floyd算法*/void

Floyd(Graph

&G){ int

D[10][10],P[10][10][10];//P[v][w][k]為TRUE，則從v到w的最短路徑中含有k節(jié)點(diǎn)//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