Extending和矩阵乘法 EXTEND-SHORTEST-PATHS(L,W) ??? 1 n =L.rows 2 let L'=()be a new n x n matrix 真的一样吗？ 3 fori Iton 4 for j Ito n 5 6=0∞ 6 for k I to n 并将W中的∞换为0 7 号=mink+w 8 return L' SQUARE-MATRIX-MULTIPLY(A,B) 17(m-1) 1 n A.rows 2 let C be a new n x n matrix b 3 for i Ito n 4 forj=Iton 5 =0 min 6 fork 1 to n 7 C=C+ak· 8 return C
Extending和矩阵乘法 并将W中的换为0 ？？？ 真的一样吗？
FASTER-ALL-PAIRS-SHORTEST-PATHS(W) 1 n= W.rows 2 L() =W 3 m=1 4 while m<n-1 5 let L(2m)be a new n x n matrix 6 L(2m) =EXTEND-SHORTEST-PATHS(L (),L(m)) ）一次“扩” 7 m 2m 的可不只是 8 return L(m) 一条边了。 Because each of the g(n-1)matrix products takes (n)time,FASTER- ALL-PAIRS-SHORTEST-PATHS runs in (nlg n)time.Observe that the code is tight,containing no elaborate data structures,and the constant hidden in the O-notation is therefore small 这段话是什么意思？
这段话是什么意思? 一次“扩” 的可不只是 一条边了