1、8.3 单源最短路径给定带权有向图G =(V,E)G =(V,E)，其中每条边的权是非负实数。另外，还给定V V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。1 1、算法基本思想DijkstraDijkstra算法是解单源最短路径问题的贪心算法。8.3 单源最短路径其基本思想是，设置顶点集合S S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S S当且仅当从源到该顶点的最短路径长度已知。初始时，S S中仅含有源。设u u是G G的某一个顶点，把从源到u u且中间只经过S S中顶点的路称为从源到u u的特殊
2、路径，并用数组distdist记录当前每个顶点所对应的最短特殊路径长度。DijkstraDijkstra算法每次从V-SV-S中取出具有最短特殊路长度的顶点u u，将u u添加到S S中，同时对数组distdist作必要的修改。一旦S S包含了所有V V中顶点，distdist就记录了从源到所有其它顶点之间的最短路径长度。8.3 单源最短路径例如，对右图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中。8.3 单源最短路径迭代S Su udist2dist2 dist3dist3 dist4dist4 dist5dist5初始1-10maxint301
3、001 11,221060301002 21,2,44105030903 31,2,4,33105030604 41,2,4,3,5510503060Dijkstra算法的迭代过程： 初始状态下，S S中只有一个点（源点v1v1）。-11-1110 01010303010010010000s:distance:path:第二步，将S S外距离S S最近的点v2v2加入S S。更新相应信息。-11-1110 01010303010010010000s:distance:path:1602第三步，将S S外距离S S最近的点v4v4加入S S。更新相应信息。-112110 010106030301
4、0010011000s:distance:path:1504904第四步，将S S外距离S S最近的点v3v3加入S S。更新相应信息。-114140 01010503030909011010s:distance:path:1603第五步，将S S外距离S S最近的点v5v5加入S S。更新相应信息。-114130 01010503030606011110s:distance:path:1 void Dijkstra ( int GN,int v0,int distance, int path，int n) /源点v0到其他顶点的最短距离distance和最短路径下标path int *s=n
5、ew intn; int minDis, i, j, u; /初始化三个数组 /逐次将各点加入S /在当前还未找到最短路径的顶点集中 选取具有最短距离的顶点u /标记顶点u已从集合T加入到集合S中 /修改从v0到其他顶点的最短距离和最短路径 void Dijkstra ( int GN,int v0,int distance, int path，int n) / / 从 源 点 v 0 到 其 他 顶 点 的 最 短 距 离distance和最短路径下标path int *s=new intn; int minDis , i, j, u; /初始化三个数组 for(i=0;in;i+) dis
6、tancei=Gv0i; si=0; if(I != v0 & distanceiMAX) pathi=v0; else pathi=-1; sv0=1;/标记顶点v0已从集合T加入到集合S中 /在当前还未找到最短路径的顶点集中选取具有最短距离的顶点u for(i=1;in;i+) minDis=MAX; for(j=0;j=n;j+)u到j有边相连，j才有可能因u的加入而距离源点更近 if(sj=0&distancejminDis) u=j; minDis=distancej; su=1;/标记顶点u已从集合T加入到集合S中 /修改从v0到其他顶点的最短距离和最短路径 for(j=0;jn;
7、j+) if( sj=0&GujMAX& distanceu+Guj4-3-5方法一：重复调用Dijkstra算法n次 可轮流以每一个顶点为源点，重复调用狄克斯特拉算法函数Dijkstra() n次，即可求得所有顶点之间的最短路径和最短距离。 利用Dijkstra()函数求所有顶点之间的最短路径算法如下。其中，distanceij中存放着从顶点i到顶点j的最短距离，pathij中存放着从顶点i到顶点j的最短路径的前一顶点下标。 voidShortPath(AdjMWGraph &G, int *distance, int *path) Int n=G.NumOfVertices(); for(
8、inti=0;in;i+) Dijkstra(G,i,distancei,pathi); 由于狄克斯特拉算法的时间复杂度是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的距
9、离。 子问题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走会更近？ 如果从顶点
10、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 )12328196123L= 0 2 9 0 68 1 0计算过程123281960 2 9 0 68 1 0D0 =0 2 98 0 61 3 0D1 =0
11、2 88 0 61 3 0D2 =0 2 87 0 61 3 0D3 =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 取最小值6D132:从顶点3到顶点2的距离（可以经过顶点1）（1）不经过顶点1： 仍是D032= ；（2）过顶点1： D031+D012=1+2=3 取最小值3D213:从顶点1到顶点3的距离（也可以经过顶点2）（1
12、）不经过顶点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);
