减少算法时间的复杂性

Question

这是我的伪代码，我想减少这段代码的时间复杂度。我是Java和算法的新手。请帮助我。

Func1(int n, int W[1..n, 1..n]) 
{ 
array d[1..n, 1..n] 
for i = 1 to n do 
{ // initialize 
    for j = 1 to n do { 
     d[i,j] = W[i,j] 
     pred[i,j] = null 
    } 
} 
for k = 1 to n do // use intermediates {1..k} 
for i = 1 to n do // ...from i 
for j = 1 to n do // ...to j 
if (d[i,k] + d[k,j]) < d[i,j]) 
{ 
    d[i,j] = d[i,k] + d[k,j] // new shorter path length 
    pred[i,j] = k // new path is through k 
} 
return d // matrix of final distances 
} 

Answer 1

这就是所有对最短路径的Floyd-Warshall算法。它是O（V^3），你不会比O（V^3）快。对于稀疏图，Dijkstra的算法可能会更快。 （对于密集图，它会更慢。）