0
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Commented Jun 15, 2017 at 17:05

1 Answer 1

Reset to default
1
$\begingroup$

Draw the tree you're given and add all edges from the initial graph in a different color (e.g. red). Then the tree is a shortest-path tree of the graph (there might be several of them) iff. no red edge breaks "the shortest-path structure", i.e. iff. it is never faster to go through a red edge than only through tree edges.

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$$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.