怎么从路-1去计算珊 我们有W矩阵！我们可以考察W上的计算序列 1m-1) L(D) = L().W W」 ) L(2) 三 L(1).W W2 1m) L(3) = L(2).W w3 min + L(n-1) Ln-2).W= Wn-1. 注意：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 -1 W) 6 return L(-1) f L)= 33 304 83050 aI06 L= 030 28 30410 105 21506 4712 0 0
只需要扩展n-2次 O(n4 )