53第8章图第8讲-最短路径和Dijkstra算法

考虑带权有向图，把一条路径（仅仅考虑简单路径）上所经边的权值之和定义为该路径的路径长度或称带权路径长度。8.5.1路径的概念从源点到终点可能不止一条路径，把路径长度最短的那条路径称为最短路径。vv1v2uc1c2c3cm路径长度=c1+c2+…+cm路径：（v，v1，v2，…，u）1/21问题描述：给定一个带权有向图G与源点v，求从v到G中其他顶点的最短路径，并限定各边上的权值大于或等于0。8.5.2从一个顶点到其余各顶点的最短路径单源最短路径问题：Dijkstra算法2/21设G=(V，E)是一个带权有向图，把图中顶点集合V分成两组：狄克斯特拉（Dijkstra）求解思路SvU=V-Su第1组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径v，…，u，就将u加入到集合S中，直到全部顶点都加入到S中，算法就结束了）。第2组为其余未求出最短路径的顶点集合（用U表示）。3/21每一步求出v到U中一个顶点u的最短路径，并将u移动到S中。直到U为空。（1）初始化：，S只包含源点即S={v}，v的最短路径为0。U包含除v外的其他顶点，U中顶点i距离为边上的权值（若v与i有边v，i）或∞（若i不是v的出边邻接点）。狄克斯特拉算法的过程SvU=V-Siv与U中顶点i的边4/21（2）从U中选取一个距离v最小的顶点u，把u加入S中（该选定的距离就是vu的最短路径长度）。SvU=V-Suv与U中顶点u的边最小5/21（3）以u为新考虑的中间点，修改U中各顶点j的最短路径长度：若从源点v到顶点j（j∈U）的最短路径长度（经过顶点u）比原来最短路径长度（不经过顶点u）短，则修改顶点j的最短路径长度。SvU=V-Suj两条路径进行比较：若经过u的最短路径长度更短，则修正6/21顶点vj的最短路径长度＝MIN(cvk+wkj，cvj)SvU=V-Sujuvjcvu……cvj边wujvj的路径：不经过顶点u经过顶点u修改方式7/21（4）重复步骤（2）和（3）直到所有顶点都包含在S中。vj考虑中间其他所有顶点k，通过比较得到vj的最短路径k8/21如何存放最短路径长度：用一维数组dist[j]存储！源点v默认，dist[j]表示源点顶点j的最短路径长度。如dist[2]=12表示源点顶点2的最短路径长度为12。如何存放最短路径：从源点到其他顶点的最短路径有n-1条，一条最短路径用一个一维数组表示，如从顶点05的最短路径为0、2、3、5，表示为path[5]={0,2,3,5}。所有n-1条最短路径可以用二维数组path[][]存储。？算法设计（解决2个问题）9/21改进的方法是采用一维数组path来保存：若从源点vj的最短路径如下：则一定是从源点vu的最短路径？vuj…a…avu……vuj…a…b反证法证明：而通过b的路径更短，则v→…a→…u→j不是最短路径是vu的最短路径与假设矛盾，问题得到证明。vj最短路径中j的前一个顶点10从path[j]推出的逆路径：j，w，u，v对应的最短路径为：v→u→w→jvwjpath[j]=wuvj的最短路径:path[w]=upath[u]=v11/210132456476168566241SUdist[]path[]01234560123456{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}Dijkstra算法示例演示最小的顶点：1最小的顶点：212/210132456476168566241SUdist[]path[]01234560123456{0,1,2}{3,4,5,6}{0,4,5,6,11,9,∞}{0,0,1,0,1,2,-1}Dijkstra算法示例演示最小的顶点：3{0,1,2,3}{4,5,6}{0,4,5,6,11,9,∞}{0,0,1,0,1,2,-1}最小的顶点：5{0,1,2,3,5}{4,6}{0,4,5,6,10,9,17}{0,0,1,0,5,2,5}13/210132456476168566241SUdist[]path[]01234560123456Dijkstra算法示例演示最小的顶点：4{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,5,4}{6}{0,4,5,6,10,9,16}{0,0,1,0,5,2,4}最小的顶点：6{0,1,2,3,5,4,6}{}{0,4,5,6,10,9,16}{0,0,1,0,5,2,4}最终结果14/21狄克斯特拉算法如下（v为源点编号）：voidDijkstra(MatGraphg，intv){intdist[MAXV]，path[MAXV];ints[MAXV];intmindis,i,j,u;for(i=0;ig.n;i++){dist[i]=g.edges[v][i];//距离初始化s[i]=0;//s[]置空if(g.edges[v][i]INF)//路径初始化path[i]=v;//顶点v到i有边时elsepath[i]=-1;//顶点v到i没边时}s[v]=1;//源点v放入S中dist和path数组初始化15/21for(i=0;ig.n;i++)//循环n-1次{mindis=INF;for(j=0;jg.n;j++)if(s[j]==0&&dist[j]mindis){u=j;mindis=dist[j];}s[u]=1;//顶点u加入S中for(j=0;jg.n;j++)//修改不在s中的顶点的距离if(s[j]==0)if(g.edges[u][j]INF&&dist[u]+g.edges[u][j]dist[j]){dist[j]=dist[u]+g.edges[u][j];path[j]=u;}}Dispath(dist,path,s,g.n,v);//输出最短路径}狄克斯特拉算法的时间复杂度为O(n2)。找最小路径长度顶点u调整16/21求06的最短路径长度：013245646168566241path[6]=4path[4]=5path[5]=2path[2]=1path[1]=0到源点最短路径为：0→1→2→5→4求06的最短路径：dist={0,4,5,6,10,9,16}0123456从顶点06的最短路径长度为16path={0,0,1,0,5,2,4}0123456利用dist和path求最短路径长度和最短路径17/21S={0,1,2,3,5,4,6}dist={0,4,5,6,10,9,16}源点v=0观察求解结果递增45691016源点到各个顶点的最短路径长度按顶点进入S的先后顺序，最短路径长度越来越长。一个顶点一旦进入S后，其最短路径长度不再改变（调整）。结论：012345618/2119/2120/21━━本讲完━━21/21