I know how to calculate the shortest paths from source
s to all other reachable vertices in a DAG (with no negative weight on the edges)
By iterating the topological sort of the graph and
relax each adjacent vertices. Which take
However - I'm required to determine if a certain spanning tree is the shortest-path tree of some directed (may be cyclic) graph in time
I've got a hint from my professor to use the algorithm to find shortest paths... but I fail to see how that helps me. All I've gotten so far is just building the shortest-path tree and comparing it with the tree given and return true or false.