This is question from CLRS Chapter 24.
Actually how to verify is already answered as below.
But I try to prove that verification is correct.
Also, I want to know this algorithm is also works if we allow negative weight edges if there is no negative cycle.
The key part of proof will be if those two main conditions are met, then they are actual instance of shortest path.
1) $d(s,v)\leq d(s,u)+w(u,v)$ for all edges $(u,v) \in E$.
2) $d(s,v)=d(s,\pi(v))+w(\pi(v),v)$ for all $v \in V$.
Other) $d(s,s)=0$, Check predecessor tree is actually spanning tree.
Converse of this statement is easy because we can use triangle equation on path.
Q1. But I think proof of this is not easy. I want to prove this rigorously.
Q2. Also this is in Dijkstra algorithm exercise, but I think those above conditions are enough for graph for allowing negative edges. Because I think non-negativity weight is only required for getting correct answer for Dijkstra algorithm.
Is this true?
Best Answer
After some thinking, I figured out how to prove it.
To avoid confusion, let $x_v$ be weight of shortest path $s$ to $v$, and $d(v)$ be actual distance, $d(v)=d(s,v)$.
First condition and $x_s=0$ implies $\displaystyle d(t)=\sum_{(u,v) \in p}w(u,v)\geq \sum_{(u,v) \in p}(x_v-x_u)=x_t-x_s=x_t$.
So, $x_t\leq d(t)$ for all vertices.
Second condition gives actual instance of such path, and it is guaranteed that it's actual shortest path by above. Note that no nonnegativity condition is used, so it also works for such as Bellman-Ford algorithm.