Check whether a directed, rooted spanning tree is actually some shortest-paths tree in $O(V + E)$ time Given a directed graph $G = (V, E)$, with all edge weights being non-negative, someone has written a program that he/she claims implements Dijkstra's algorithm.
For a fixed starting vertex $s$, the program produces $v.d$ (shortest distance from $s$) and $v.\pi$ (immediate predecessor in the shortest path) for each vertex $v \in V$. 


  Question: How to check whether the $d$ and $\pi$ values match those of some shortest-paths tree of $G$ in linear time (i.e., $O(V + E)$)? 




My attempts:


Feed the $d$ and $\pi$ values into a running instance of our real Dijkstra algorithm and check if some step would go wrong.
The key point here is how to reduce the running time of the real Dijkstra algorithm from $O(E \log V)$ to $O(V + E)$, taking advantage of the existing $v.d$ and $v.\pi$ values.
To check the triangle inequality condition: For all edges $(u,v) \in E$, we have $d(s,v) \le d(s,u) + w(u,v)$.    


  Question: However, is the triangle inequality condition a sufficient one for some directed, rooted spanning tree to be a shortest-paths tree?
Hint: 


This question is telling us to find an algorithm in $O(V+E)$ which immediately suggests us some kind of search in the graph, i.e, DFS.
Using $\pi$ we should be able to build a candidate tree $T$ rooted in $s$ to test if it's shortest-path tree.
In each shortest-path tree, we have that for every $v \in V(T)$, $v \neq s$, the equality $d(\pi(v)) + w(\pi(v), v) = d(v)$ holds.