0
$\begingroup$

I'm looking at Dijkstra's algorithm in the introduction to algorithms book by Cormen, which calculates the optimal path for each vertex starting from a source.

Unlike the implementation of the algorithm in Wikipedia where they save previous nodes in optimal path from source in the prev array and update the array at every relaxation,the algorithm in the book only Relaxes the edges and doesn't save the previous vertex.

Is there a way to use the output of Dijkstra's algorithm from the book and after that to populate the prev array without modifying the algorithm in the book? the algorithm from the book

$\endgroup$
  • $\begingroup$ Can you upload a screenshot or picture of the algorithm your taking about? Without seeing the algorithm you're discussing, it's hard to say if the shortest path can be found without modifying the algorithm or not. $\endgroup$ – Noble Mushtak Jan 5 at 14:52
  • $\begingroup$ Here it is in the question now $\endgroup$ – user3133165 Jan 5 at 14:56
  • $\begingroup$ What does RELAX(u,v,w) do? $\endgroup$ – Hagen von Eitzen Jan 5 at 15:05
1
$\begingroup$

Once your algorithm has computed the distance to $s$ for all vertices, you can compute (a possible choice of) $prev$ in $O(|E|)$:

For each directed edge $(u,v)$, if $\operatorname{dist}(v)=\operatorname{dist}(u)+\operatorname{cost}(u,v)$, set $\operatorname{prev}(v)=u$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.