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?