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)$)?
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?