This is from CLRS problem 24.3-5:
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 $\mathrm{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.
All the answers I find online, explain how to solve this problem, but not why their solution is correct.
Let us look at what we need to do:
- We need to make sure that for the source node $s$ we have $s.d = 0$ and $v.\pi = \emptyset$. This can be done in $\mathrm{O}(1)$ time.
- We need to verify that the $\pi$ table corresponds to a tree. This is simple, we just build the undirected graph corresponding to the $\pi$ table, and then run a DFS traversal to see if the graph has cycles or not. Can be done in $\mathrm{O}(V+E)$ time.
- For every node $u$ not reachable from $s$, it must be the case that $u.\pi = \emptyset$ and $u.d = \infty$. Another simple check, find everything you can reach in the tree that you drew in step 2, and for every other node do the checking. Another $\mathrm{O}(V+E)$ term.
- For every edge $(u,v)$ in the shortest path tree it must be true that, $v.d = u.d + w(u,v)$. Check to ensure that this is the case. Because the professor might put random guesses for the distance values that turned out to be correct, but they had absolutely no connection to the shortest path tree given.
Everything until this point is 100% simple and clear. But the last point, is what I find difficult to argue about.
- Relax every edge of $G$ exactly once, if any distance values change, then the shortest path tree given is wrong, if all stay the same then it is correct.
Why is this true? How to prove that if indeed the shortest path tree is wrong, relaxing every edge of $G$, no matter the order, will definitely improve at least one of the distance values?
