Gauge Goodman

Computers & Technology

12 February, 05:19

Professor Gaedel has written a program that he claims implements Dijkstra's algorithm. The program produces v. d and v.Π for each vertex v  V. Give 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.