只需要扩展-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 )
问题5： 为什么上述算法被称为“慢” 算法，为什么它可能被加快？ In-1 =In =In+i
𝐿 𝑛−1 = 𝐿 𝑛 = 𝐿 𝑛+1 …