《最短路径算法》由会员分享，可在线阅读，更多相关《最短路径算法（30页珍藏版）》请在金锄头文库上搜索。
1、8.3 单源最短路径,给定带权有向图G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。 1、算法基本思想 Dijkstra算法是解单源最短路径问题的贪心算法。,8.3 单源最短路径,其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。 初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长
2、度。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最近的点
3、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
4、/在当前还未找到最短路径的顶点集中 选取具有最短距离的顶点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& dis
5、tanceu+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、6,1 2 3,L=,0 2 9 0 6 1 0,复习Dijkstra算法,其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。 初始时，S中仅含有源点。设u是G的某一个顶点，把从源点到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组distance记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组distance作必要的修改。一旦S包含了所有V中顶点，distance就记录了从源到所有其它顶点之间的最短路径长度。,算法中，我们不断更
7、新以下三个数组： s数组: si，当顶点i加入S时，si置1 Distance数组: Distancei记录原点到 顶点i的最短特殊路径长度。 path数组： pathi记录顶点i在其最短特殊路径上的前驱顶点。由该数组可求得原点到各点的最短路径。如：设源点是顶点1, path数组如下,例如，对右图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中。,s:,distance:,path:,由源点1到顶点5的路径为：1-4-3-5,方法一：重复调用Dijkstra算法n次,可轮流以每一个顶点为源点，重复调用狄克斯特拉算法函数Dijkstra() n次，即可求
8、得所有顶点之间的最短路径和最短距离。 利用Dijkstra()函数求所有顶点之间的最短路径算法如下。其中，distanceij中存放着从顶点i到顶点j的最短距离，pathij中存放着从顶点i到顶点j的最短路径的前一顶点下标。,voidShortPath(AdjMWGraph ,由于狄克斯特拉算法的时间复杂度是O(n2)，所以n次调用狄克斯特拉算法的时间复杂度是O(n3)。,该问题具有最优子结构性质,例如上图中，若路线I和J是A到C的最优路径，则根据最优化原理，路线J必是从B到C的最优路线。,子问题的构造,原问题：每个顶点到其他所有顶点的最短距离 最小的子问题D0：从顶点i （不得经过任何其他顶
9、点）到顶点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（
10、可以经过顶点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，有些点间的距离是否会变的更近。,例：考虑下图所示的带权有向图，求所
11、有顶点之间的最短距离。,V =,(,b,),(,a,),1 2 3,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的距离
12、（也可以经过顶点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); ,
