最短路径算法ppt课件.ppt
8.3 单源最短路径,给定带权有向图G=(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。1、算法基本思想Dijkstra算法是解单源最短路径问题的贪心算法。,8.3 单源最短路径,其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。,8.3 单源最短路径,例如，对右图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中。,8.3 单源最短路径,Dijkstra算法的迭代过程：,初始状态下，S中只有一个点（源点v1）。,s:,distance:,path:,第二步，将S外距离S最近的点v2加入S。更新相应信息。,s:,distance:,path:,1,60,2,第三步，将S外距离S最近的点v4加入S。更新相应信息。,s:,distance:,path:,1,50,4,90,4,第四步，将S外距离S最近的点v3加入S。更新相应信息。,s:,distance:,path:,1,60,3,第五步，将S外距离S最近的点v5加入S。更新相应信息。,s:,distance:,path:,1,void Dijkstra(int GN,int v0,int distance,int path，int n)/源点v0到其他顶点的最短距离distance和最短路径下标path int*s=new intn;int minDis,i,j,u;/初始化三个数组,/逐次将各点加入S/在当前还未找到最短路径的顶点集中 选取具有最短距离的顶点u/标记顶点u已从集合T加入到集合S中/修改从v0到其他顶点的最短距离和最短路径,void Dijkstra(int GN,int v0,int distance,int path，int n)/从源点v0到其他顶点的最短距离distance和最短路径下标path int*s=new intn;int minDis,i,j,u;/初始化三个数组 for(i=0;in;i+),distancei=Gv0i;si=0;if(I!=v0 j+),if(sj=0j+)if(sj=0&GujMAX&distanceu+Gujdistancej),distancej=distanceu+Guj;pathj=u;,2、算法的正确性和计算复杂性(1)贪心选择性质(2)最优子结构性质(3)计算复杂性对于具有n个顶点和e条边的带权有向图，如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要 时间。这个循环需要执行n-1次，所以完成循环需要 时间。算法的其余部分所需要时间不超过。,7.5所有点对的最短路径问题,对于一个各边权值均大于0的有n个顶点的带权有向图G=(V,E)，求所有顶点之间的最短路径和最短距离。,图的邻接矩阵表示法,3,V=,(,b,),(,a,),2,9,6,123,L=,0 2 9 0 61 0,复习Dijkstra算法,其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源点。设u是G的某一个顶点，把从源点到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组distance记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组distance作必要的修改。一旦S包含了所有V中顶点，distance就记录了从源到所有其它顶点之间的最短路径长度。,算法中，我们不断更新以下三个数组：s数组:si，当顶点i加入S时，si置1Distance数组:Distancei记录原点到 顶点i的最短特殊路径长度。path数组：pathi记录顶点i在其最短特殊路径上的前驱顶点。由该数组可求得原点到各点的最短路径。如：设源点是顶点1,path数组如下,例如，对右图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中。,s:,distance:,path:,由源点1到顶点5的路径为：1-4-3-5,方法一：重复调用Dijkstra算法n次,可轮流以每一个顶点为源点，重复调用狄克斯特拉算法函数Dijkstra()n次，即可求得所有顶点之间的最短路径和最短距离。利用Dijkstra()函数求所有顶点之间的最短路径算法如下。其中，distanceij中存放着从顶点i到顶点j的最短距离，pathij中存放着从顶点i到顶点j的最短路径的前一顶点下标。,voidShortPath(AdjMWGraph,由于狄克斯特拉算法的时间复杂度是O(n2)，所以n次调用狄克斯特拉算法的时间复杂度是O(n3)。,该问题具有最优子结构性质,例如上图中，若路线I和J是A到C的最优路径，则根据最优化原理，路线J必是从B到C的最优路线。,子问题的构造,原问题：每个顶点到其他所有顶点的最短距离最小的子问题D0：从顶点i（不得经过任何其他顶点）到顶点j的距离；子问题D1：从顶点i（可以经过顶点1，不得经过其他任何其他顶点）到顶点j的距离。,子问题Dk：从顶点i（可以经过顶点1、顶点2、顶点k，不得经过任何其他顶点）到顶点j的距离。子问题Dn：从顶点i（可以经过顶点1、顶点2、顶点n）到顶点j的距离。即原问题,递推关系的建立,由di,jk-1推出di,jk的过程如下若k=0,di,jk=Lij(因为从i到j不允许经过任何其他顶点）若1k n,di,jk=mindi,jk-1,di,kk-1+dk,jk-1,子问题Dk-1：从顶点i（可以经过顶点1、顶点2、顶点k-1）到顶点j的距离。子问题Dk：从顶点i（可以经过顶点1、顶点2、顶点k-1、顶点k）到顶点j的距离。,从子问题Dk-1：到子问题Dk，仅仅多考虑了一个顶点k。我们需要重新考虑从i到j的距离：顶点i到顶点j，是不是从k走会更近？,如果从顶点i到顶点j从顶点k走更近，则i到j的距离di,jk=i到k的距离di,kk-1+k到j的距离dk,jk-1 如果顶点i到顶点j从顶点k走更远，甚至走不通，则保持原来的距离不变 di,jk=di,jk-1。,由di,jk-1推出di,jk的过程，主要考虑的是顶点k的加入会引起什么变化？由不允许路过顶点k到允许路过顶点k，有些点间的距离是否会变的更近。,例：考虑下图所示的带权有向图，求所有顶点之间的最短距离。,V=,(,b,),(,a,),123,L=,计算过程,Di,jk：从顶点i（可以经过顶点1、顶点2、顶点k）到顶点j的距离。,在D1中，第1行和第一列是不变的，因为说从顶点1到顶点j或顶点j到顶点1：允许经过顶点1是没有意义的,D123:从顶点2到顶点3的距离（可以经过顶点1）（1）不经过顶点1：仍是D023=6；（2）过顶点1：D021+D013=8+9=17 取最小值6,D132:从顶点3到顶点2的距离（可以经过顶点1）（1）不经过顶点1：仍是D032=；（2）过顶点1：D031+D012=1+2=3 取最小值3,D213:从顶点1到顶点3的距离（也可以经过顶点2）（1）不经过顶点2：仍是D113=9；（2）过顶点2：D112+D123=2+6=8 取最小值8,算法设计,重要发现：在从Dk-1到Dk的计算过程中中，第k行和第k列是不变的。（因为说从顶点k到顶点j或顶点j到顶点k允许经过顶点k是没有意义的）,而在从Dk-1到Dk的计算过程中也只用到第k行和第k列，也就是说，在这一步的计算过程中用到的数据都不会被覆盖。故在算法中仅使用一个矩阵D即可,FLOYD算法,FLOYD(int*L,int n)int*D=(int*)malloc(n+1)*(n+1)*sizeof(int);D L 将数组L复制到D;for(k=0;kn;k+)for(i=0;in;i+)for(j=0;jn;j+)Di*n+j=min(Di*n+j,Di*n+k+Dk*n+j);,
