2
$\begingroup$

Suppose we are given a directed weighted graph $G=(V,E)$, a source vertex $s$ and the value of the cheapest path $\delta(s,v)$ for every $v \in V$.

I want to find an algorithm for the shortest path tree rooted in $s$ with time complexity of $O(V+E)$.

We may assume that all vertices are reachable from $s$.

I thought of running something like BFS traversal on $G$ and for each vertex $u$ I examine, for each neighbor $v$ of him, I'll check that $\delta(u)+w(u,v)=\delta(v)$ and if so, I'll add $(u,v)$ to the output SPT.

Is that sounds right? or has any pitfalls I haven't thought about? If so, how would you prove that? by induction?

$\endgroup$
2
$\begingroup$

Use a proof by induction on the length of the paths. In other words, prove first that you've found a correct shortest path for all vertices that can be reached by a shortest path of length 1; then that you've found a correct shortest path for all vertices that can be reached by a shortest path of length 2; and so on.

$\endgroup$
  • $\begingroup$ thanks, so the overall algorithm sounds correct? $\endgroup$ – chen doytshman May 8 at 16:34
  • $\begingroup$ @chendoytshman, if you try to prove it correct in this way, you'll be able to find out for yourself! $\endgroup$ – D.W. May 8 at 16:35
  • $\begingroup$ If you prove it, it is correct. $\endgroup$ – Evil May 8 at 16:36
  • $\begingroup$ sounds legit. thank you. $\endgroup$ – chen doytshman May 8 at 16:38

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.