Professor Gaedel has written a program that he claims implements Dijkstras algorithm. The program produces .d and

Professor Gaedel has written a program that he claims implements Dijkstra’s algorithm. The program produces ν.d and ν.π for each vertex ν ∈ V. Give an O(V + E)-time algorithm to check the output of the professor’s program. It should determine whether the d and π attributes match those of some shortest-paths tree. You may assume that all edge weights are nonnegative.