Consider a directed graph G = [V; E] with edge weights w(u, v) for (u, v) ∈ E.
Suppose some one gives you values for {d[v], Π[v]}}; v∈V. and claims that these an the length of the shortest path and the predecessor node in it for v∈V.
How would you verify if this statement is true or false using an efficient algorithm that does not solve the entire shortest path problem from scratch? What is the complexity of your algorithm?
26.2-9
26-1
26-1