# 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?