图的最短路径

图的最短路径7月17日3.5图的最短路径【知识点】掌握图的传递闭包、最短路的概念。掌握最短路的求解方法，理解floyd算法、dijkstra算法的适用范围，最短路算法的灵活应用。【知识讲解】3.5.1图的传递闭包求解问题：对于图G的任意顶点i和j，是否存在一条从i到j的路径（即i和j是否可达）？（1）对于图G的任意一个顶点u，u可达的顶点集合称为u的传递闭包。在无向图中，u的传递闭包为和u处于同一连通分量的点集。有向图中，u的传递闭包为u可达的顶点集合。1234657123465711110001111000111100011110000000111000011100001110110000101000011010000010000000001000001010000010邻接矩阵G*Gi和j是否有边相连？i和j是否有路相连（可达）？（2）求解传递闭包的算法判断结点i到j是否有路径，只有两种情况：①结点i到j有边，则有路径。②i到j之间没有边：如果存在另外的一个结点k，满足：i到k有路径，k到j有路径，则i到j有路径。否则i到j没有路径。则：can[i][j]=can[i][j]||(can[i][k]&&can[k][j])ijkijk初始化：can[i][j]=true:i到j有边；can[i][j]=false:i到j无边。can[i][i]=true；求解过程：for(intk=1;k=n;k++)枚举中间点for(inti=1;i=n;i++)枚举起点for(intj=1;j=n;j++)枚举终点can[i][j]=can[i][j]||(can[i][k]&&can[k][j]);[引例]：现在，我们想从城市A到达城市E。怎样走才能使得路径最短，最短路径的长度是多少？3.5.2图的最短路径已知各个城市之间的道路情况如下：12345678910115312384385523438AE图中两点间的最短距离两类问题：1、图中每对顶点（任意两点）之间的最短路径（弗洛伊德算法：floyed）。2、图中一个顶点到其他顶点的最短路径（单源最短路径）（dijkstra算法、Bellman-ford算法、SPFA算法）。3.5.3计算每一对顶点间的最短路径（floyd算法）（一）求最短距离目标：把图中任意两点i与j之间的最短距离都求出来d[i][j]。原理：任意一个最短路算法都是基于这样一个事实：从任意节点A到任意节点B的最短路径不外乎2种可能：1是直接从A到B，2是从A经过若干个节点到B。if(d[i][k]+d[k][j]d[i][j])d[i][j]=d[i][k]+d[k][j]算法思想：设顶点集S(初值为空)，用数组D的每个元素D[i][j]保存从Vi只经过S中的顶点到达Vj的最短路径长度。①初始时令S={}，D[i][j]的赋初值方式是：②将图中一个顶点Vk加入到S中，修改D[i][j]的值，修改方法是：D[i][j]=Min{D[i][j],(D[i][k]+D[k][j])}原因：从Vi只经过S中的顶点(Vk)到达Vj的路径长度可能比原来不经过Vk的路径更短。③重复②，直到G的所有顶点都加入到S中为止。算法实现：for(intk=1;k=n;k++)for(inti=1;i=n;i++)for(intj=1;j=n;j++)if(d[i][k]+d[k][j]d[i][j])d[i][j]=d[i][k]+d[k][j];初始化条件：D[i][i]=0;//自己到自己为0；对角线为0；D[i][j]=边权，i与j有直接相连的边D[i][j]=+∞，i与j无直接相连的边。//如果是int数组，采用memset(d,0x7f,sizeof(d))可全部初始化为一个很大的数举例：已知下图中给定的关系，顶点个数n=100,两点之间的距离w=1000,求给定两点之间的最短距离.要求：输出最短距离d[1][5]。分析：D[i][j]:表示顶点i到顶点j之间的最短距离。初始化如下：515122313171549235241345702317∞49230513∞1750∞∞∞13∞0749∞∞70floyed02217354222051320175018253513180742202570初始状态：02317∞49230513∞1750∞∞∞13∞0749∞∞70终止状态：02217354222051320175018253513180742202570k=1:02317∞49230513721750∞66∞13∞0749726670k=2:02317364923051372175018663613180749726670k=3:02217354922051371175018663513180749716670k=4:02217354222051320175018253513180742202570参考代码：#includeiostream#includecstringusingnamespacestd;constintmaxn=101;constintmaxw=1001;intd[maxn][maxn];intn,p,q;voidinit(){cinn;cinpq;for(inti=1;i=n;i++)for(intj=1;j=n;j++)if(i==j)d[i][j]=0;elsed[i][j]=maxw;inti,j,k;while(cinijk){d[i][j]=k;d[j][i]=k;}}voidfloyed(){for(intk=1;k=n;k++)for(inti=1;i=n;i++)for(intj=1;j=n;j++)if(d[i][k]+d[k][j]d[i][j])d[i][j]=d[i][k]+d[k][j];};voidprint(){coutd[p][q]endl;}intmain(){init();floyed();print();return0;}（二）floyed输出最短路径路线方法一：定义二维数组Path[n][n](n为图的顶点数)，元素Path[i][j]保存从Vi到Vj的最短路径所经过的顶点。①初始化为Path[i][j]=-1，表示从Vi到Vj不经过任何(S中的中间)顶点。②当某个顶点Vk加入到S中后使A[i][j]变小时，令Path[i][j]=k。若Path[i][j]==k：从Vi到Vj经过Vk，最短路径序列是(Vi,…,Vk,…,Vj)，则路径子序列：(Vi,…,Vk)和(Vk,…,Vj)一定是从Vi到Vk和从Vk到Vj的最短路径。从而可以根据Path[i][k]和Path[k][j]的值再找到该路径上所经过的其它顶点，…依此类推。参考代码：for(intk=1;k=n;k++)for(inti=1;i=n;i++)for(intj=1;j=n;j++)if(d[i][k]+d[k][j]d[i][j]){d[i][j]=d[i][k]+d[k][j];path[i][j]=k;};初始化：path[i][j]=-1;i与j不经过任何中间点d[i][j]：02317∞49230513∞1750∞∞∞13∞0749∞∞70path[i][j]：-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1d[i][j]：02317∞49230513∞1750∞∞∞13∞0749∞∞70path[i][j]：-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1k=1:02317∞49230513721750∞66∞13∞0749726670path[i][j]：-1-1-1-1-1-1-1-1-11-1-1-1-11-1-1-1-1-1-111-1-1k=2:02317364923051372175018663613180749726670path[i][j]：-1-1-12-1-1-1-1-11-1-1-1212-12-1-1-111-1-1k=3:02217354922051371175018663513180749716670k=4:02217354222051320175018253513180742202570path[i][j]：-13-13-13-1-1-13-1-1-1213-12-1-1-131-1-1path[i][j]：-13-1343-1-1-14-1-1-1243-12-1-1444-1-1输出i到j的最短路径：voiddfs(inti,intj){//输出i到j之间的点，不包含i和j结点；if(path[i][j]!=-1){dfs(i,path[i][j]);coutpath[i][j]'';dfs(path[i][j],j);};};主程序：输出i;dfs(i,j);输出j;path[i][j]：-13-1343-1-1-14-1-1-1243-12-1-1444-1-1终止状态：02217354222051320175018253513180742202570dfs(1,5)=dfs(1,4),输出4,dfs(4,5)dfs(1,3),3,dfs(3,4)path(4,5)=-1,返回上一层path(1,3)=-1,返回上一层dfs(3,2),2,dfs(2,4)输出：13245拓展：以右图为例，演示用floyed算法求任意一对顶点间最短路径过程。方法二：设path[i][j]记录i到j的最短路径中j的前驱顶点。如样例：1--4:35:1324path[1][4]=2path[1][2]=3path[1][3]=1参考代码：for(intk=1;k=n;k++)for(inti=1;i=n;k++)for(intj=1;j=n;j++)if(d[i][k]+d[k][j]d[i][j]){d[i][j]=d[i][k]+d[k][j];path[i][j]=path[k][j];};初始化：i到j有边，则path[i][j]=i;path[j][i]=j;输出i到j的路线voiddfs(inti,intj){if(i==j)couti'';elseif(path[i][j]0){dfs(i,path[i,j]);coutj'';};};d[i][j]：02317∞49230513∞1750∞∞∞13∞0749∞∞70path[i][j]：0110120220330000400450050k=1:02317∞49230513721750∞66∞13∞0749726670path[i][j]：0110120221330010400451150k=2:02317364923051372175018663613180749726670path[i][j]：0112120221330212420451150k=3:02217354922051371175018663513180749716670k=4:02217354222051320175018253513180742202570path[i][j]：0312130221330213420453150path[i][j]：0312430224330243420434250参考代码：for(intk=1;k=n;k++)for(inti=1;i=n;k++)for(intj=1;j=n;j++)if(d[i][k]+d[k][j]d[i][j]){d[i][j]=d[i][k]+d[k][j];path[i][j]=path[k][j];};初始化：i到j有边，则path[i][j]=i;path[j][i]=j;输出i到j的路线voiddfs(inti,intj){if(i==j)couti'';elseif(path[i][j]0){dfs(i,path[i,j]);cou