S7.6.2所有点对间的最短路径问题 §7.6.2所有点对间的最短路径问题 Floyd算法的基本步骤 ■解法一 定义nXn的方阵序列D_-,D。:.Da-中 以每一顶点为源点，调用Dljkstra]算法，时间o(n内 ◆韧抛化1D-,=C ·解法二 D-门叩=边<P的长度，表示初谢的从到的量短略径长虚，即它是从 F1oyd(1978年量现莫得主)算法更前清，但是时间仍为0(n习 到的中间不经过其他中间点的量短路径， 假设，加权邻被矩阵C(n×n) ◆选代：设Dk-,已求出，如何得到D,(0≤k≤n一1)？ o 谱问 Dk-门门表示从到的中间点不大于k一1的量细路径p:1.: c 计<P不是边 考律将项点k加入路径即得到顶点序列qi.k.可， w(<i,j)otherwise 费干六精为留上- ◆思想 IJ∈V,若<J>∈E,测从到南一条路径，长度为C间门。 乐绿舞经点不大于一尚准造显 景及鞋牌 D]=min{D.[D-m[k]+D-[k]0]) 到更短的路径。 矩阵序列D-D6,…D。-可在同1个矩阵上选代求得，为什么？ §7.6.2所有点对间的最短路径问题 S7.6.2所有点对间的最短路径问题 Floyd算法的基本步霖 Floyd算法实现 ◇解矩阵 void Floyd(AdjMatrix D,AdjMatrix C,int Path[n][n]) for (i=0;i<n;i++) Path[nJ[n]:记录路径构造 for(j户0：jKn;j计+)（初输化 在第k次跌代中，P门叮记录从到的中间点序号不大于k D[[=C[[: 的量短路径上顶点的后键顶点。 if C[]=Infinity Path[=-1; 当算法结束时，可由Path叮们得到从到的最短路径，其 else Path[时所是i的后健 方法是从顶点开始反复找其后罐，直至找到顶点或确认到 Mendfor for(k=0;k<n:k+)将k扩充到从到的量短路径上 没有路径为止。 for i=0;i<n;++) for (j=0:j<n;j++) f(D[Ik灯+D[k灯[<D[[)( D[(=D[灯+D[k[小：修效略径长度 Pat曲h[[=Path】Ik灯：修政廉径 S7.62所有点对间的最短路径问题 ■Floyd算法实现 void PrintPath(AdjMatrix D,int Path[n][)不妨设D是蓝矩时 for (E0;kn;+) for(J=0;n;++){ prn“%d,D】方到的绿烟哪径长底 next=Path[]Nn 为点的后 什(next=,1)n无后健爽示剩无略径 printf (%d to %d no path.In",I,)t else pin“%d",i)方输出起点 while next = print“->%d,next片输出后项点 next-Path[next刘0：银蝶线后鞭顶点 】fendwhile pin“%->%d",J:物出峰点 }lendif }endfor 33 13 §7.6.2 所有点对间的最短路径问题 „ 解法一 以每一顶点为源点，调用DIjkstra算法，时间O(n3) „ 解法二 Floyd（1978年图灵奖得主）算法更简洁，但是时间仍为O(n3) ™ 假设：加权邻接矩阵C（n×n） 0 if i=j C[i][j]= ∞ if <i,j>不是边 w(<i,j>) otherwise ™ 思想： ∀i,j∈V，若<i,j>∈E，则从i到j有一条路径，长度为C[i][j]。 但它不一定是最短路径，因为可能存在一条从i到j中间包含其他顶点的 更短路径。因此，必须依次考虑能否在i和j之间加入顶点0,1…,n-1,而得 到更短的路径。 14 §7.6.2 所有点对间的最短路径问题 „ Floyd算法的基本步骤 定义n×n的方阵序列D－1, D0 , … Dn－1, ™ 初始化： D－1＝C D－1[i][j]＝边<i,j>的长度，表示初始的从i到j的最短路径长度，即它是从i 到j的中间不经过其他中间点的最短路径。 ™ 迭代：设Dk－1已求出，如何得到Dk（0≤k≤n－1）？ Dk－1[i][j]表示从i到j的中间点不大于k－1的最短路径p：i…j， 考虑将顶点k加入路径p得到顶点序列q：i…k…j， 若q不是路径或q是长度大于p长度的路径，则当前的最短路径仍是上一步 结果：Dk[i][j]= Dk－1[i][j]；否则用q取代p作为从i到j的最短路径。 因为q的两条子路径i…k和k…j皆是中间点不大于k－1的最短路径， 所以从i到j中间点不大于k的最短路径长度为： Dk[i][j]＝min{ Dk－1[i][j], Dk－1[i][k] +Dk－1[k][j] } 矩阵序列D－1, D0 , … Dn－1可在同1个矩阵上迭代求得，为什么？ 15 §7.6.2 所有点对间的最短路径问题 „ Floyd算法的基本步骤 ™解矩阵： Path[n][n]：记录路径构造 在第k次跌代中，P[i][j]记录从i到j的中间点序号不大于k 的最短路径上顶点i的后继顶点。 当算法结束时，可由Path[i][j]得到从i到j的最短路径，其 方法是从顶点i开始反复找其后继，直至找到顶点j或确认i到j 没有路径为止。 16 §7.6.2 所有点对间的最短路径问题 „ Floyd算法实现 void Floyd( AdjMatrix D, AdjMatrix C, int Path[n][n] ) { for ( i=0; i<n; i++ ) for ( j=0; j<n; j++ ) { //初始化 D[ i][ j]=C[ i][ j]; if ( C[ i][ j]=Infinity ) Path[i][j]=-1; else Path[ i][ j]=j; //j是i的后继 }//endfor for ( k=0;k<n;k++ ) //将k扩充到从i到j的最短路径上 for ( i=0;i<n;i++ ) for ( j=0;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[ i] [ k]; //修改路径 } } 17 §7.6.2 所有点对间的最短路径问题 „ Floyd算法实现 void PrintPath( AdjMatrix D, int Path[n][n] ) {//不妨设D是整型矩阵 for ( i=0; i<n; i++ ) for ( j=0; j<n; j++ ) { printf( “%d”, D[ i][ j] ); //i到j的最短路径长度 next=Path[i][j]；//next为起点i的后继 if （ next == -1 ）//i无后继表示i到j无路径 printf（“%d to %d no path.\n”, i, j ）； else { printf( “%d”, i ); //输出起点 while ( next != j ){ printf( “->%d”, next ); //输出后继顶点 next=Path[next][j]; //继续找后继顶点 } //endwhile printf( “%->%d”, j ); //输出终点 } //endif } //endfor }