§7.6.1单源最短路径问题 10 §7.6.1单源最短路径问题 例子 ■如何构造最优解 100 100 因为D向量只记录了最优解的值，但不能得到量优解。因 100 301 ②20 此，要记录量优解则须引入附加信意。 因为最优解是最短路径树，故只需增加一个向量P0.-1]: ② ①30 ③0 量短距离：红色 用P可记录顶点的双亲，由双亲的唯一性知，顶点的康短路 估计距离：白色 径可从P可反复上期至根（源点）即可求得最优解。 依次求出的距离 ■算法实现 0(0 1)D[0- 90 60 2)D叫-10，题项点2 10 33-30,点2， 计<1j>不是边 5o② 203 )D叫2-50，调项点4 5)D4-60 G= w(<i,j>)otherwise 最短略径铜：各顶点的量短略径（实辣）总是一操以源点为极的树，称之 为最短径制 §7.6.1单源最短路径问题 for(i=0:iKn-1:t+)(向红点编s扩充n-1个红点 min=Infinity: void Dijkstra AdjMatrix G,Distance D,Path P,int s for(j户0；j水n:j计+)i选估计距离最小的白点k(离s绿近) 0≤s≤n-i,若iP不是边，测G可=Infinity if (IS[j]&&D[j]<min ) Boolean S[n:S是红点靠，S门为真囊示j为红点，香剩为白点 min=D[j];k=j for(i户0；iKn;it+)(谢化 if(min=Infinity)return;l自点集为空或只剩下无最知路径的点 S[=FALSE; S[k]=TRUE:∥k加入红点集 D叮=GS]门：量物输的估计距童 for(j户0：j长n:jt+)调雕测徐白点的估计距离 if (IS[j]&&D[j]>D[k]+G[k][j]){ f(D门<nfinity）P可=s;s是的前厦履亲) D[j门=DK+Gj小：修改白点的估计距离，使之离s更近 else P门=-1；∥无前图，注意Ps)亦无前驱 P[j】=k:∥k是的前星 Mlendfor Ss]=TRUE;D[S]=O:红点靠仅有源点s ■算法执行过理 ■构造解 原点s=3 精出路径及其长度 铺环 红点集S D[O]D[1]D[2]D[3]D[4] POPI1)P2P3)P间 void PrintPath(Path P,Distance D)(路径是逆向的 inti,pre; 初始化 3) °20060 11313 for(=0:iK;i计+)（依次打印点的量短路径及长度 43-12 printf(nD:%d,P:%d”,D0,:输出鳞点i 3,2 pre=P门：I/找绕点的前驱 3,24 4 1 2 while pre=-1){ printf(",%d”,preH 同上 白点靠0,1)中所有点的估 pre=Ppro:I上测找前驱 计距离为©，退出量环 时间：时间0（的 。构造解 2 22 7 §7.6.1 单源最短路径问题 „ 例子 0 1 2 4 3 0 10 100 100 ∞ 30 30 10 0 1 2 4 3 0 10 100 100 60 30 50 10 30 0 1 2 3 4 10 30 100 20 50 10 60 0 1 2 4 3 0 10 90 60 50 30 20 10 30 0 1 2 4 3 0 10 60 10 50 30 20 10 30 最短距离：红色 估计距离：白色 依次求出的最短距离为： 1) D[0]=0 2) D[1]=10，调整顶点2 3) D[3]=30，调整顶点2，4 4) D[2]=50，调整顶点4 5) D[4]=60 ¾ 最短路径树：各顶点的最短路径（实线）总是一棵以源点为根的树，称之 为最短路径树。 8 §7.6.1 单源最短路径问题 „ 如何构造最优解 因为D向量只记录了最优解的值，但不能得到最优解。因 此，要记录最优解则须引入附加信息。 因为最优解是最短路径树，故只需增加一个向量P[0..n-1], 用P[i]记录顶点的双亲，由双亲的唯一性知，顶点i的最短路 径可从P[i]反复上溯至根（源点）即可求得最优解。 „ 算法实现 ∞ if <i,j>不是边 G[i][j]= w(<i,j>) otherwise 9 §7.6.1 单源最短路径问题 void Dijkstra ( AdjMatrix G, Distance D, Path P, int s ){ //0≤s ≤n-1,若<i,j>不是边，则G[i][j]=Infinity Boolean S[n]；//S是红点集。S[i]为真表示j为红点，否则为白点 for ( i=0; i<n; i++) { //初始化 S[i]=FALSE; D[i]=G[s][i]; //置初始的估计距离 if ( D[i]<Infinity ) P[i]=s; //s是i的前驱(双亲) else P[i]=-1; // i无前驱，注意P[s]亦无前驱 } S[s]=TRUE; D[s]=0；//红点集仅有源点s 10 for ( i=0; i<n-1; i++) { //向红点集S扩充n－1个红点 min=Infinity; for ( j=0; j<n; j++ ) //选估计距离最小的白点k（离s最近） if ( !S[ j ]&&D[ j ]<min ) { min=D[ j ]; k=j; } if (min==Infinity) return; // 白点集为空或只剩下无最短路径的点 S[k]=TRUE; // k加入红点集 for ( j=0; j<n; j++ ) //调整剩余白点的估计距离 if ( !S[ j ]&&D[ j ]>D[k]+G[k][ j ] ) { D[ j ] = D[k]+G[k][ j ]; //修改白点j的估计距离，使之离s更近 P[ j ] = k; // k是j的前驱 } }//endfor } 11 „ 算法执行过程 源点s＝3 „ 时间：时间O(n2) „ 构造解 白点集{0,1}中所有点的估 计距离为∞，退出循环 3 同上 － 2 {3,2,4} 4 ∞ ∞ 20 0 30 -1 -1 3 -1 2 1 {3,2} 2 ∞ ∞ 20 0 30 -1 -1 3 -1 2 初始化 {3} － ∞ ∞ 20 0 60 -1 -1 3 -1 3 循环i 红点集S k D[0] D[1] D[2] D[3] D[4] P[0] P[1] P[2] P[3] P[4] 0 1 2 3 4 10 30 100 20 50 10 60 12 输出路径及其长度 void PrintPath（Path P，Distance D）{ //路径是逆向的 int i，pre; for ( i=0; i<n; i++ ) { //依次打印点i的最短路径及长度 printf(“\nD:%d, P:%d”, D[i], i); //输出终点i pre=P[i]; //找终点i的前驱 while ( pre != -1 ) { printf( “, %d”, pre ); pre=P[pre]; //上溯找前驱 } } } „ 构造解