-3

这是我的伪代码,我想降低这段代码的时间复杂度。我是 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
}
4

1 回答 1

1

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

于 2013-10-19T10:31:45.347 回答