怎么从册-1去计算野 E∑aik·bk 我们有W矩阵！我们可以考 k=1 察W上的计算序列 SQUARE-MATRIX-MULTIPLY(A,B) 1 n A.rows 2 let C be a new n x n matrix /(m-1) L( = L(o).W =W, 3 for i=1 to n D → b L2) L().W =W2. 4 for j=1to n 1m) →c, L(3) = L2).W W3, 5 C)=0 min→+， 十→· Lm-)= L-2).W=Wn-1. 6 for k 1 to n 7 Ci=CU+aik·bkj 8 return C 注意：Wn-1不是W矩阵的n-1次幂！
怎么从𝑙 𝑖𝑗 𝑚−1去计算𝑙 𝑖𝑗 𝑚 我们有W矩阵！我们可以考 察W上的计算序列 注意：Wn-1不是W矩阵的n-1次幂！
只需要扩展-2次 SLOW-ALL-PAIRS-SHORTEST-PATHS(W) 1 n=W.rows 2L0=W 8 3 for m 2to n-I 4 let L)be a new nxn matrix 5 】 L EXTEND-SHORTEST-PATHS(L -W) 6 return L(-1) f L)= 33 304 83050 aI06 L= 030 28 30410 10 21506 4712 0 0
只需要扩展n-2次 𝑶(𝒏𝟒)