# shortest path tree algorithm

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?

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.

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