floyd算法精讲

1、floyd(弗洛伊德弗洛伊德)算法算法弗洛伊德算法的基本思想13:02:15(1)给出网络的邻接矩阵D，令D(0)=D,其元素为dij(0) 不相连，相连jijijildijij,0,)0(邻接矩阵13:02:15v1V3V4V226184图图108480124106260)0(D弗洛伊德算法的基本思想(2)在原路径里增加一个新结点，如果产生的新路径比原路在原路径里增加一个新结点，如果产生的新路径比原路径更小，则用新路径值代替原路径的值。这样依次产生径更小，则用新路径值代替原路径的值。这样依次产生n个矩阵（个矩阵（n为网络结点数）为网络结点数）)()3()2()1(,nDDDD用公式表示就是，

2、对于用公式表示就是，对于K=1,2,3n,第第k个矩阵个矩阵,min)1()1()1()(kkjkikkijkijdddd)()(kijkdD运算过程中运算过程中K从从1开始，而开始，而 i，j 则分别从则分别从1到到n取遍所有取遍所有值，然后值，然后k加加1，直到，直到k等于等于n时停止。时停止。13:02:15弗洛伊德算法演示弗洛伊德算法演示ABDC1232271长度长度0123001712022023130路径路径01230ABAD1BABC2CD3DADB0321( 1) . Di jG arcsi j13:02:16ABDC12322710321长度长度012300171202202

3、310路径路径01230ABAD1BABC2CD3DA(0)( 1)( 1)( 1) , 00 Di jM in Di j DiDj(0)( 1)( 1) 1 3 , 1 0 0 3 ,27 ,99DM inDDM inM in(0) 3 13,112DM in92 3BADDAB弗洛伊德算法演示弗洛伊德算法演示13:02:16(1)(0)(0)(0) 3 2 3 2 , 3 1 1 2 ,2 24DM i n DDDM i n ABDC12322710321长度长度01230017120292023120路径路径01230ABAD1BABCBAD2CD3DA(1)(0)(0)(0) , 1

4、1 Di jM in Di j DiDj(1)(0)(0)(0) 0 2 0 2 , 0 1 1 2 , 1 23DM i n DDDM i n 3 4ABCDABCDAB弗洛伊德算法演示弗洛伊德算法演示13:02:16ABDC12322710321长度长度01230013120220231240路径路径01230ABABC1BABC2CD3DADABDABC(2)(1)(1)(1) 1 3 1 3 , 1 2 2 3 9,2 24DM i n DDDM i n(2)(1)(1)(1) , 2 2 Di jM in Di j DiDj(2)(1)(1)(1) 0 3 0 3 , 0 2 2 3

5、 7,3 25DM i n DDDM i n7954ABCDBCDADBAD弗洛伊德算法演示弗洛伊德算法演示13:02:16FLOYD算法步骤算法步骤算法：算法：FLOYD输入输入: 维矩阵维矩阵 ，其中有向图，其中有向图 中的边中的边 的长度为的长度为 。输出输出: 矩阵矩阵 ，使得，使得 等于等于 i 到到 j 的最短路径长度。的最短路径长度。(step 0) D l ; /将有向网的邻接矩阵输入到将有向网的邻接矩阵输入到D中中(step 1) for k = 1 to n(step 3) for i = 1 to n(step 5) Di, j = minDi, j, Di, k + Dk, j(step 6) end for(step 8) end for(step 4) for j = 1 to n(step 7) end fornn