floyd算法精讲

floyd(弗洛伊德)算法,弗洛伊德算法的基本思想,*,(1)给出网络的邻接矩阵D，令D,(0),=D,其元素为d,ij,(0),邻接矩阵,*,v1,V3,V4,V2,2,6,1,8,4,图,1,弗洛伊德算法的基本思想,(2),在原路径里增加一个新结点，如果产生的新路径比原路径更小，则用新路径值代替原路径的值。这样依次产生,n,个矩阵（,n,为网络结点数）,用公式表示就是，对于,K=1,2,3n,第,k,个矩阵,运算过程中,K,从,1,开始，而,i,，,j,则分别从,1,到,n,取遍所有值，然后,k,加,1,，直到,k,等于,n,时停止。,*,弗洛伊德算法演示,A,B,D,C,1,2,3,2,2,7,1,0,3,2,1,*,A,B,D,C,1,2,3,2,2,7,1,0,3,2,1,9,2,3,BAD,DAB,弗洛伊德算法演示,*,A,B,D,C,1,2,3,2,2,7,1,0,3,2,1,3,4,ABC,DABC,DAB,弗洛伊德算法演示,*,A,B,D,C,1,2,3,2,2,7,1,0,3,2,1,7,9,5,4,ABCD,BCD,AD,BAD,弗洛伊德算法演示,*,FLOYD,算法步骤,算法：,FLOYD,输入,:,维矩阵 ，其中有向图,中的边 的长度为 。,输出,:,矩阵 ，使得 等于,i,到,j,的最短路径长度。,(step 0) D,l,; /,将有向网的邻接矩阵输入到,D,中,(step 1) for,k,= 1 to n,(step 3) for,i,= 1 to n,(step 5) D,i,j, = minD,i,j, D,i,k, + D,k,j,(step 6) end for,(step 8) end for,(step 4) for j = 1 to n,(step 7) end for,算法复杂度为,O(n3),算法小结,*,