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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ thanks, so the overall algorithm sounds correct? $\endgroup$
    – chendoy
    May 8, 2019 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, 2019 at 16:35
  • $\begingroup$ If you prove it, it is correct. $\endgroup$
    – Evil
    May 8, 2019 at 16:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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