next up previous
Next: Proof Up: Alternative Algorithm for Shortest Previous: Base Case

Algorithm 


   \( D \left[u, v, 0\right] = \left\{
 \begin{array}{l@{\quad,\quad}l}
 0 & u = ...
...t(u, v\right) & uv \in E \\
\infty & \mathrm{otherwise}
\end{array}\right. \) 


for \( u = 1 \;\mathrm{to}\; n \) 


for \( v = 1 \;\mathrm{to}\; n \) 


for \( k = 1 \;\mathrm{to}\; n \) 

\( \tilde{D} \left[u, v, k\right] = \min \left\{ \tilde{D} \left[u, v, k-1\right], \tilde{D} \left[u, k, k-1\right] + \tilde{D} \left[k, v, k-1\right] \right\} \)

This algorithm is obviously $O\left(n^3\right)$!

I also went through the algorithm to find out the optimum path given $D$. As someone in class pointed out, it is much more efficient to just store the path as you take it, and keep the final iteration of the big matrix around at the end to reconstruct it. As an added benefit, we keep only $2 O(n^2)$ storage and use $O(n)$ time to reconstruct the path, as opposed to $O(n^3)$ storage and $O(n^2)$ time to reconstruct. If you were in class you saw the algorithm, otherwise you will have to figure it out yourself (or read it in the text?).


Raymond Fingas 2002-01-18