Check whether a directed, rooted spanning tree is actually some shortest-paths tree in $O(V + E)$ time

Question

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:

1. 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.

2. 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?

Answer 1

Hint:

1. 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.
2. Using $\pi$ we should be able to build a candidate tree $T$ rooted in $s$ to test if it's shortest-path tree.
3. 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.

Answer 2

We can prove this in a similar way to how you prove Bellman-Ford has converged. Let $d(v)$ be the distance from root to $v$ in this rooted spanning tree and let $\delta(v)$ be the shortest distance from $s$ to $v$ in the graph. If $d(v) = \delta(v)$, then attempting to relax all edges in $E$ should not change anything. When I say "relax" I mean, invoke the triangle inequality:

relax(u, v):
  if d(v) > d(u) + w(u,v):
    d(v) = d(u) + w(u,v)
    pi(v) = u

If, at any point, a relaxation changes $d(v)$, then clearly the spanning tree path is not the shortest. This makes sense intuitively, but we can prove it formally.

Claim: If $d(v) > \delta(v)$ for some node $v$, then some node $v'$ on the true shortest path from $s$ to $v$ has value $d(v')$ such that $d(v') > d(u) + w(u,v')$ for some edge $(u,v') \in E$.

Proof: By induction on the number of nodes $n$ in the shortest path from $s$ to $v$.

Base Case: When we have $n = 2$, then we have one edge in the shortest path $s \rightarrow v$. Thus, the true shortest path has distance $w(s,v)$. If $d(v) > \delta(v)$ then:

$$\begin{align*} d(v) &> \delta(v)\\ & = w(s,v)\\ & = d(s) + w(s,v) \end{align*}$$

Inductive Case: Assume the claim holds for the first $n-1$ nodes on the shortest path $\{s, u_1, u_2, \ldots, u_{n-2}, v\}$. We now prove it holds for the addition of $v$ to the shortest path.

If the claim holds for this whole path, then either some node prior to $v$ in the path triggers the if condition, and the claim holds by induction. Otherwise, we have for all nodes $u$ prior to $v$ that $d(u) = \delta(u)$ and $d(v) > \delta(v)$. Now we need only prove that $d(v) > d(u_{n-2}) + w(u_{n-2}, v)$:

$$\begin{align*} d(v) &> \delta(v)\\ & = \delta(u_{n-2}) + w(u_{n-2}, v) & \text{by construction of the shortest path}\\ & = d(u_{n-2}) + w(u_{n-2}, v) \quad \square \end{align*}$$

Thus, after running the relaxation step on all edges, you should have your answer.