CLRS Exercise 24.3-4 - Confirm Output of a Program Claiming to Implement Dijkstra's Algorithm I'm trying to better understand Question 24.3-4 From CLRS below: 


  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)$ 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 non-negative.


I have the answer from the Solutions manual, but simply do not understand how this answer actually works: (bottom of pg. 5/19, Exercise 24.3-4 didn't want to overload the question with a long solution):
https://sites.math.rutgers.edu/~ajl213/CLRS/Ch24.pdf

Basically, the solution says we have to check every edge $(u, v)$ for all $v \neq s$. I understand that we only need to ensure that $s.d = 0$ and $s.\pi = NIL$ since the $\delta(s, s) = 0$ and $s$ should not have a predecessor, as it is the first vertex in the graph. The solution goes on to mention that: 


  "Check that $v.\pi$ is the vertex which minimizes $u.d +w(u, v)$ for all vertices $u$ for which there is an edge $(u, v)$, and that $v.d = v.π.d + w(v.π, v)$. If this is ever false, return false"


So I understand that for any $v \neq s$ that $v.\pi.d &lt; v.d$ by the fact that $v.d = v.\pi.d + w(v.pi, v)$ so the distance of any node's predecessor must always be less than that of the node by the simple property. 

How do we manage to check though that: "$v.\pi$ is the vertex which minimizes $u.d +w(u, v)$ for all vertices $u$ for which there is an edge $(u, v)$?" 

Since say we pick some random vertex in the graph that is a neighbor of $s$, call this node $v$. So $\delta(s, v)$ could potentially be calculated by traversing half of the graph then coming back to $v$ through some other node, $u$ if the $w(s, v)$ is extremely large. How does the algorithm verify cases like this? Does it ensure that it starts only at the neighbors of $s$ first, verify those distances, and essentially inductively proceed to verify the remaining predecessors and distances? 

It seems that for $v \in V - {s}$ that if $v.\pi$ is correct, then all that remains is to verify $v.d$? I just don't really understand how the algorithm can correctly do this.. Is it traversing the graph, or iterating over the adjacency list/set of edges for each node, such that for a node, $v$ we check all edges $(u, v)$ somehow and then come up with an understanding of whether the node $v$ has the proper $v.\pi$? 

Could someone please help/explain how this solution works? Have been struggling for a few hours now on this, and stepped through the algorithm with written examples but am not seeing the pattern here. Thank you.

Edit I've seen some answers mentioning creating a tree (since Dijkstra's algorithm is supposed to output a shorted path tree from the src node, $s$). 

Regarding this: Would we create a shortest path tree using all of the $v.\pi$ values for each $v \in V - \{s\}$, since $s.\pi = NIL$? This takes time $O(V + E)$ to create an adjacency list we would need to traverse using BFS/DFS. Then, we begin a DFS on the tree created by the $v.\pi$ attributes and modify the DFS to check $v.d = v.\pi.d + w(v.\pi.d + v)$ or something along these lines?
So I'm going to go out on a limb with this one and attempt to answer my own question. It seems that when running the algorithm given in the solution, say that there are many vertices for which $v.\pi$ and $v.d$ is incorrect (call this set of vertices, $V_i$ and $V_i \subseteq V$). 

When we run the algorithm, if there are at least some vertices for which $v.\pi$ and $v.d$ is correct (call this set of vertices $V_c$ and $V_c \subseteq V$), the algorithm is guaranteed to detect at some point that there is an incorrect vertex $u$, such that $u \in V_i$. 

But, it may return a false positive for some vertex, $u$ (again such that $u \in V_i$) if all of the parents of $u$, WLOG say a parent($u$), is called $p$, so $p$ also has incorrect distance and predecessor values, thus $p.\pi$ and $p.d$ is incorrect for a parent, $p$ of $u$ therefore $p \in V_i$ but eventually we will come across some vertex $u \in V_i$ such that when we look at the incoming edges to $u$, we will find that $u.\pi$ is incorrect, since at least $1$ of the parents of $u$, call it $p' \in V_c$ has correct distance and predecessor values, and we would return false/something that indicates we have found the vertex $u$ such that $u.\pi$ and $u.d$ are incorrect. 

In the case of all $v \in V$ outputted by the Professor's program are incorrect, we'd easily find a $v$ such that $s \xrightarrow{} v$ and see that $v.\pi$ or $v.d$ is incorrect. 

I believe this explains how the algorithm works... Someone please correct me where/if I'm wrong. Thanks.