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?
Best Answer
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$.