数据结构课件-第七章图5最短路径

学习目标①

掌握图的基本概念，包括图、有向图、无向图、完全图、子图连通图、度、入度、初度、简单回路和环等基本概念的定义。②

重点掌握图的各种

结构、包括邻接矩阵和邻接表等③重点掌握图的基本元素、包括创建图、输出图、深度优先遍历、广度优先遍历算法等④掌握图的其他运算、包括最小生成树、最短路径、拓扑排序和关键路径等算法⑤

灵活运

图这种数据结构解决一些综合应用

。问题描述：V5V0V4V3V2V1在图中，从一个顶点到另一个顶点间可能存在多条路径，而每条路径上经过的边数并不一定相同。比如V0到V5存在3条路径V0->V5V0->V4->V5V0->V2->V3->V5最短路径为V0->V5V4V530100V060101020V3V2V1

550问题描述：如果上述的图的每条边附上权值的话，则路径长度为路径上各边的权值的总和，两个顶点间路径长度最短的那条路径称为两个顶点间的最短路径，则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的最短路径，这条路径只含一条弧，并且这条弧的权值最小。Step2：求出下一条次短路径，这条路径只可能有两种情况：或者是直接从源点到该点(只含一条弧)；

或者是从源点经过顶点v1，再到达该顶点v2(由两条弧组成)。Step3：求再下一条次短路径，它可能有三种情况：或者是直接从源点到该点

(只含一条弧)；或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是从源点经过顶点v2，再到达该顶点。Step4：依次求其他最短路径，它或者是直接从源点到该点(只含一条弧)；或者是从源点经过已求得最短路径的顶点，再到达该顶点。Dijkstra算法——Single

Source/All

Destinations设置辅助数组D，其中每个分量 表示当前所求得的从源点到其余各顶点

k的最短路径。一般情况下，D

[k]=<源点到顶点k的弧上的权值>或者=<源点到其它顶点的路径长度>+<其它顶点到顶点k

的弧上的权值>。1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。V0和k之间存在弧V0和k之间不存在弧INFINITYD[k

]

G.arcs

[v0][k

]2）修改其它各顶点的D

[k]值。假设求得最短路径的顶点为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为图中顶点个数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,则算法结束，否则转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];//计数变量，计算共选择节点多少个//保存依次被选中的节点edge

lo

thcost[6];

//初始值为矩阵的第一行char

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

//以初始节点开始计算最短路径

(路径)for(int

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

lo

thcost[i].cost=g.cost[0][i];//初始化为M，最短路径长度为矩阵的第一行权值if(g.cost[0][i]!=M){lo

thcost[i].adjvex=0;//有数据则adjvex置为cout<<"初始存在路径的是"<<lo

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

}}int

min;

//保存最小权值int

minvex;

//保存最小权值边的另一顶点int

selected[6]={0};

//次变量是作为控制已输出的节点不再参与的判断参数//此时adjvex[1]为，存放依次选出cout<<endl<<"开始选择顶点："<<endl;for(int

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

//要选择的次数,除掉起点{

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<<"

. "

<<"对应的边上的权值是"<<min<<endl;

}selected[minvex]=1;

//已参与的节点就置为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

<<"

的最短路径经历的节点依次是："<<path[eadjvex]<<"

长度是："<<lo

thcost[eadjvex].cost<<endl;}

}每一对顶点之间的最短路径问题的提法：已知一个各边权值均大于0的带权有向图，对每一对顶点vi

vj，要求求vi

与vj之间的最短路径和最短路径长度。解决办法:

算法，其主要思想是从

vi到

vj的所有可能存在的路径中，选出一条长度最短的路径。算法将有向图G=(V,E)，用邻接矩阵cost存放另外设置一个二维数组A，存放当前顶点之间的最短路径定义A[i][j]表示当前顶点vi到顶点vj的最短路径长度算法的思想递推产生矩阵序列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:初始状态，A-

=A-1

=路径：ABACBABCCAAB640

4

113

02311CABACBABCCACABcost

=Step2:加入A点考虑，经过A的路径有CAB和BAC，则修改CB距离从

变为7，而BAC的距离长于BC，则BC距离不改。6

0

23

7

0A0

=路径：0

4

116

0

23

0算法演示AB64Step3:加入B点考虑，经过B的路径有ABC，路径为6<AC,修改AC的距离从11到6231166

0

23

7

0A1

=路径：ABABCBABCCACABCStep4:加入C点考虑，经过C的路径有BCA，路径为5<BA,修改BA的距离从6到5cost

=A2

=路径：0

4

116

0

23

00

4

653

7

0BAB

ABCBCACCA

CAB结论：经过4次迭代后，矩阵A中存放的是各个顶点间的最短路径/*Floyd算法*/void

Floyd(Graph

&G){ int

D[10][10],P[10][10][10];//P[v][w][k]为TRUE，则从v到w的最短路径中含有k节点//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