How to verify a shortest path tree with O(V+E) running time by giving node's predecessor and shortest distance The question in  described as follows:

Professor Gaedel has written a program that he claims implements
  Dijkstra’s algorithm. The program produces $v.d$ and $v.\pi$ for each vertex
  $v\in V$. Give an $O.(V + E)$-time algorithm to check the output of the
  professor’s program. It should determine whether the $d$ and $\pi$
  attributes match those of some shortest-paths tree. You may assume
  that all edge weights are nonnegative.

v.d is the shortest distance from starting node to $v.$ $v.\pi$ is $v$'s predecessor in the shortest path from starting node to $v$.
FYI: this question was originally asked on StackOverflow but not solved.
https://stackoverflow.com/questions/13558800/verify-dijkstras-algorithm-in-o-v-e
 A: Also we can assume that graph $G$ is connected. Let $s$ be the starting vertex,  $n$ be the number of vertices and $m$ be the number of edges. At first it should be verified that function $\pi\colon V\setminus \{\,s\,\} \to V$ of parents in the tree really produces a tree, i. e. there is no sequence $v_1, \ldots, v_k$ of vertices that $v_1 = \pi(v_2)$, $\ldots$, $v_{k-1} = \pi(v_k)$ and $v_k = \pi(v_1)$. It is tree if and only if each vertex can be attained from $s$ passing from parent $\pi(v)$ to vertex $v$ only. Use one DFS from $s$ to check attainability of all vertices, requires $\mathrm O(n)$ time.
Then you should check for each vertex $v$ that the for all neighour vertices $u$ inequality $d(s, u) \le d(s, v) + w_{uv}$ holds ($d(a, b)$ is the distance between vertices $a$ and $b$ and $w_{ab}$ is the weight of edge $\{\,a, b\,\}$), i. e. for all vertices distance can not be reduced. It should be checked for each egde once, so requires $\mathrm O(m)$ time again.
There are two more conditions: distance from vertex $s$ to itself should be zero and distance to any other vertex $v$ should be equal to distance to it's parent $\pi(v)$ plus weight of edge, connecting them. Checking the first of these conditions requires $\mathrm O(1)$ time and checking the second one requires $\mathrm O(n)$ time.
All condition together:
$$\begin{cases}
\pi(\pi(\ldots\pi(v)\ldots)) = s & \forall v \in V(G) \,\\
d(s, u) \le d(s, v) + w_{uv} & \forall u \in N_G(v),\\
d(s, s) = 0,\\
d(s, v) = d(s, \pi(v)) + w_{v\pi(v)} & \forall v \in V(G) \setminus \{\,s\,\}.
\end{cases}$$
Totally we need $\mathrm O(m)$ time for the connected graph $G$. If need of any condition or sufficiency of their aggregate are not obvious, ask in comments.
