《数据结构,第7章-7最短路径ppt》由会员分享，可在线阅读，更多相关《数据结构,第7章-7最短路径ppt（29页珍藏版）》请在金锄头文库上搜索。
1、7.7 最短路径 7.7.1 路径的概念 在一个无权的图中,若从一顶点到另一顶点存在着一条路径,则称该路径长度为该路径上所经过的边的数目,它等于该路径上的顶点数减1。由于从一顶点到另一顶点可能存在着多条路径,每条路径上所经过的边数可能不同,即路径长度不同,我们把路径长度最短(即经过的边数最少)的那条路径叫做最短路径,其路径长度叫做最短路径长度或最短距离。,对于带权的图,考虑路径上各边上的权值，则通常把一条路径上所经边的权值之和定义为该路径的路径长度或称带权路径长度。从源点到终点可能不止一条路径，把带权路径长度最短的那条路径称为最短路径,其路径长度(权值之和)称为最短路径长度或者最短距离。,7.
2、7.2 从一个顶点到其余各顶点的最短路径 问题：给定一个带权有向图G与源点v0，求从v0到G中其他顶点的最短路径，并限定各边上的权值大于或等于0。 Dijkstra 提出了一种按路径长度递增的次序产生最短路径的算法。,Dijkstra算法思想 基本思想是：设G=(V,E)是一个带权有向图, 把图中顶点集合V分成两组： 第一组为已求出最短路径的顶点集合S(初始时S中只有一个源点，以后每求得一条最短路径v0,vk,就将vk加入到集合S中,直到全部顶点都加入到S中,算法就结束了) 第二组为其余未确定最短路径的顶点集合U。 按最短路径长度的递增次序依次把U中的顶点加入S中。在加入的过程中,总保持从源点
3、v0到S中各顶点的最短路径长度不大于从源点v0到U中任何顶点的最短路径长度。 为每个顶点定义一个辅助参量：距离,S中顶点距离就是从v0到此顶点的最短路径长度,U中顶点距离从v0到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。,Dijkstra算法的具体步骤： 设S为已经求得的最短路径的顶点集合，disti表示v0到vi的最短路径。 (1)S=v0，disti=cost v0vi (2)选择u，使得distu=mindisti | vi不在S中 则u为当前求得的一条从v0出发的最短路径的终点，让 S=S+u (3)修改所有不在S中的顶点Vi的最短路径长度 if distu+costuvid
4、isti distvi= distu+costuvi (4)重复步骤(2)和(3)直到所有顶点都包含在S中。,S U v0到06各顶点的距离 0 1,2,3,4,5,6 0,4,6,6, 0,1 2,3,4,5,6 0,4,5,6,11, 0,1,2 3,4,5,6 0,4,5,6,11,9, 0,1,2,3 4,5,6 0,4,5,6,11,9, 0,1,2,3,5 4,6 0,4,5,6,10,9,17 0,1,2,3,5,4 6 0,4,5,6,10,9,16 0,1,2,3,5,4,6 0,4,5,6,10,9,16 则v0到v1v6各顶点的最短距离分别为4、5、6、10、9和16。,
5、Dijkstra算法如下(n为图G的顶点数,v0为源点编号)： void Dijkstra(int costMAXVMAXV,int n,int v0) int distMAXV,pathMAXV; int sMAXV;int mindis,i,j,u; for (i=0;in;i+) disti=costv0i; /距离初始化 si=0; /s置空 if (costv0iINF) /路径初始化 pathi=v0; else pathi=-1; sv0=1;pathv0=0; /源点编号v0放入s中,for (i=0;in;i+) /循环直到所有顶点的最短路径都求出 mindis=INF; u
6、=-1; for (j=0;jn;j+) /选取不在s中且具有最小距离的顶点u if (sj=0 /输出最短路径 ,S U v0到06各顶点的距离 pathi 0 1,2,3,4,5,6 0,4,6,6, 0,0,0,0,-1,-1,-1 0,1 2,3,4,5,6 0,4,5,6,11, 0,0,1,0,1,-1,-1 0,1,2 3,4,5,6 0,4,5,6,11,9, 0,0,1,0,1,2,-1 0,1,2,3 4,5,6 0,4,5,6,11,9, 0,0,1,0,1,2,-1 0,1,2,3,5 4,6 0,4,5,6,10,9,17 0,0,1,0,5,2,5 0,1,2,3,
7、5,4 6 0,4,5,6,10,9,16 0,0,1,0,5,2,4 0,1,2,3,5,4,6 0,4,5,6,10,9,16 0,0,1,0,5,2,4 则v0到v1v6各顶点的最短距离分别为4、5、6、10、9和16。,void Ppath (int path,int i,int v0) /前向递归查找路径上的顶点 int k; k=pathi; if (k=v0) return; /找到了起点则返回 Ppath(path,k,v0); /找k顶点的前一个顶点，递归 printf(“%d,”,k); /输出k顶点 ,void Dispath(int dist,int path,int
8、s,int n,int v0) for (i=0;in;i+) if (si=1) printf(“从%d到%d的最短路径长度为: %dt路径为:“,v0,i,disti); printf(“%d,”,v0); /输出路径上的起点 Ppath(path,i,v0); /输出路径上的中间点 printf(“%dn”,i); /输出路径上的终点 else printf(“从%d到%d不存在路径n“,v0,i); ,7.7.3 每对顶点之间的最短路径 问题：对于一个各边权值均大于零的有向图,对每一对顶点vivj,求出vi与vj之间的最短路径和最短路径长度。 可以通过以每个顶点作为源点循环求出每对顶点
9、之间的最短路径。除此之外,弗洛伊德(Floyd)提出另一个算法用于求两顶点之间最短路径。,假设有向图G=(V,E)采用邻接矩阵cost存储,另外设置一个二维数组A用于存放当前顶点之间的最短路径长度,分量Aij表示当前顶点vi到顶点vj的最短路径长度。弗洛伊德算法的基本思想是递推产生一个矩阵序列A0,A1,Ak,An,其中Akij表示从顶点vi到顶点vj的路径上所经过的顶点编号不大于k的最短路径长度。,弗洛伊德思想可用如下的表达式来描述： A0ij=costij Ak ij=min Ak-1ij Ak-1ik+Ak-1kj 0kn-1,初始时,有A0ij=costij。当求从顶点vi到顶点vj的
10、路径上所经过的顶点编号不大于k的最短路径长度时,要分两种情况考虑： 一种情况是该路径不经过顶点编号为k的顶点,此时该路径长度与从顶点vi到顶点vj的路径上所经过的顶点编号不大于k的最短路径长度相同； 另一种情况是从顶点vi到顶点vj的最短路径上经过编号为k的顶点。那么,该路径可分为两段,一段是从顶点vi到顶点vk的最短路径,另一段是从顶点vk到顶点vj的最短路径,此时最短路径长度等于这两段路径长度之和。 这两种情况中的较小值,就是所要求从顶点vi到vj的路径上所经过的顶点编号不大于k+1的最短路径。,采用弗洛伊德算法求解过程,考虑经过顶点v0,A0ij表示由vi到vj,经由顶点v0的最短路径。
11、只有从v2到v1经过v0的路径和从v2到v3经过v0的路径,且不影响v2到v1和v2到v3的路径长度,因此,有：,考虑经过顶点v1,A1ij表示由vi到vj,经由顶点v1的最短路径。存在路径v0-v1-v2,路径长度为9,将A02改为9,path02改为1,因此,有：,考虑顶点v2,A2ij表示由vi到vj,经由顶点v2的最短路径。存在路径v3-v2-v0,长度为4,将A30改为4；存在路径v3-v2-v1,长度为4,将A31改为4。存在路径v1-v2-v0,长度为7,将A10改为7。将path30、path31和path10均改为2。因此,有：,考虑顶点v3,A3ij表示由vi到vj,经由顶
12、点v3的最短路径。存在路径v0-v3-v2,长度为8比原长度短,将A02改为8；存在路径v1-v3-v2-v0,长度为6(A13+A30=2+4=6)比原长度短,将A10改为6；存在路径v1-v3-v2,长度为3,比原长度短,将A12改为3；将path02、path10后path12均改为3。因此,有：,最后求得的各顶点最短路径长度A和Path矩阵为：,从0到0路径为：0,0 路径长度为：0 从0到1路径为：0,1 路径长度为：5 从0到2路径为：0,3,2 路径长度为：8 从0到3路径为：0,3 路径长度为：7 从1到0路径为：1,3,2,0 路径长度为：6 从1到1路径为：1,1 路径长度
13、为：0 从1到2路径为：1,3,2 路径长度为：3 从1到3路径为：1,3 路径长度为：2,从2到0路径为：2,0 路径长度为：3 从2到1路径为：2,1 路径长度为：3 从2到2路径为：2,2 路径长度为：0 从2到3路径为：2,3 路径长度为：2 从3到0路径为：3,2,0 路径长度为：4 从3到1路径为：3,2,1 路径长度为：4 从3到2路径为：3,2 路径长度为：1 从3到3路径为：3,3 路径长度为：0,弗洛伊德算法如下： void Floyd(int costMAXV,int n) int AMAXVMAXV,pathMAXVMAXV;int i,j,k; for (i=0;i(Aik+Akj) Aij=Aik+Akj; pathij=k; Dispath(A,path,n); /输出最短路径 ,练习： 写出下图的邻接矩阵并计算每对顶点之间的最短路径。,本章小结 本章基本学习要点如下： (1)掌握图的相关概念,包括图、有向图、无向图、完全图、子图、连通图、度、入度、出度、简单回路和环等定义。 (2)重点掌握图的各种存储结构,包括邻接矩阵和邻接表等。 (3)重点掌握图的基本运算,包括创建图、输出图、深度优先遍历、广度优先遍历算法等。,(4)掌握图的其他运算,包括最小生成树、最短路径、拓扑排序和关键路径等算法。 (5)灵活运用图这种数据结构解决一些综合应用问题。,
