Content deleted Content added
m WPCleaner v1.26 - Repaired 1 link to disambiguation page - (You can help) - Adjacent |
Magioladitis (talk | contribs) m fixed unbalanced brackets / tidy up using AWB (9335) |
||
Line 34:
You can sort in <math>\Theta(\log n)</math> time with rank-sort. You need <math>\Theta(n^2)</math> processors, and do <math>\Theta(n^2)</math> work.
<source>
Program ranksort
declare
Line 49 ⟶ 50:
A[R[i]] := A[i] >
end
</source>
===Floyd–Warshall algorithm===
Line 54 ⟶ 56:
Using the [[Floyd–Warshall algorithm]] all pairs [[Shortest path problem|shortest path]] algorithm, we include intermediate nodes iteratively, and get <math>\Theta(n)</math> time, using <math>\Theta(n^2)</math> processors and <math>\Theta(n^3)</math> work.
<source>
Program shortestpath
declare
Line 68 ⟶ 71:
k := k + 1 if k < n - 1
end
</source>
We can do this even faster. The following programs computes all pairs shortest path in <math>\Theta(\log^2 n)</math> time, using <math>\Theta(n^3)</math> processors and <math>\Theta(n^3 \log n)</math> work.
<source>
Program shortestpath2
declare
Line 83 ⟶ 88:
D[i,j] := min(D[i,j], <min k : 0 <= k < n :: D[i,k] + D[k,j] >) >
end
</source>
After round <math>r</math>, <code>D[i,j]</code> contains the length of the shortest path from <math>i</math> to <math>j</math> of length <math>0 \dots r</math>. In the next round, of length <math>0 \dots 2r</math>, and so on.
| |||