# How to tell if a spanning tree is a shortest-spanning tree of a DAG?

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 O(V+E)

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 O(E)

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.

• What did you try? Where did you get stuck? Have you tried working through some examples? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. – D.W. Jun 15 '17 at 17:05

Therefore, if you pre-compute the distance $d_T(u)$ from the source to every node $u$ in your input tree, you just have to check, for every red edge of length $l$ between two nodes $u$ and $v$, whether:
$$d_T(v) \le d_T(u)+l$$