CLRS Exercise 24.3-4 - Confirm Output of a Program Claiming to Implement Dijkstra's Algorithm

Question

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

Answer 1

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.

Answer 2

You seem to have the right idea, but your answer is a little imprecise, so I'll give my best bid in the hope that it helps someone.

Let the source (root) of the shortest path tree be named $s$.

Firstly, I'm going to assume that the tree encoded by the $v.\pi$ and $v.d$ values is internally consistent. That is, there are no loops and $v.d$ ($v$'s distance estimate) is equal to the weight of the path from $s$ to $v$. This is easy to check in linear time. Given this assumption an incorrect distance estimate will be too large as opposed to too small; You can't find a shorter path than the shortest path, and the distance estimate is consistent with the path.

Secondly, I'd like to promote describing algorithms in a simpler way whenever possible, and save heavy mathematical notation for when it is needed. In the context of CLRS, "relaxing" an edge is meaningful, so a simpler way to describe the algorithm is:

Relax all the edges in the graph. If any distance estimate changes or if the distance estimate of the source is not zero, return that the input is not a shortest path tree. Otherwise, return that it is.

Now to prove the correctness of the algorithm.

An edge was successfully relaxed $\rightarrow $ the input is wrong:

Since some $v.d$ changed to something smaller, you discovered a shorter $s \leadsto v$ path, so the input must be wrong.

The input is wrong $\rightarrow $ an edge will be relaxed successfully:

Let $v$ be a closest vertex to $s$ which has an incorrect distance estimate. The last node $u$ before $v$ on the shortest $s\leadsto v$ path is closer to $s$ than $v$ is (because edge weights are positive) and so $u.d$ is correct (by the choice of $v$ as the closest). The edge $(u,v)$ will be relaxed, and the shortest $s \leadsto v$ path will be found, changing $v.d$.

From the above we can see that an edge will be relaxed successfully if and only if the input is incorrect, and thus the algorithm must be correct.

(I just realized this proof only works when edge weights are strictly positive, as opposed to non-negative. But I think adapting it shouldn't be too hard)