Discussion Post
The single-source shortest path algorithm we studied requires time O(|E| log |V | + |V | log |V |) time to find the minimum distance δ(v0, vi) from the source v0 to each node vi . Checking the answer seems easier than finding it. Give an O(|V |+|E|) time algorithm that, given a directed, connected, weighted graph (with nonnegative weights), and a sequence of distances di for each 0 ≤ i ≤ n, will verify whether di = δ(v0, vi), i.e. whether di really is the minimum distance from the source to vertex vi . Argue the correctness of your algorithm (i.e. prove that (i) if the di 's are the shortest path values, your algorithm returns YES, and (ii) if the di's are not correct shortest path values, your algorithm returns NO.) Explain why your algorithm is O(|V | + |E|).