A directed graph is said to be unipathic if for any two vertices u and v in the

Question

A directed graph is said to be unipathic if for any two vertices u and v in the graph G=(V,E), there is at most one simple path from u to v.

Suppose I am given a unipathic graph G such that each edge has a positive or negative weight, but contains no negative weight cycles.

From this I want to find a O(|V|) algorithm that finds all the the shortest paths to all nodes from a source node s.

I am not sure how I would go about approaching this problem. I am trying to see how I could use the fact that it contains no negative weight cycles and of course at most one simple path between any node u to v.

Explanation / Answer

Choose a data representation

First, look at the size of the result. You want the collection of shortest paths from s to every other node. Unless the average length of a path is bounded by a constant (which it isn't: any list is unipath, and if you take the root for s the total length of the paths is n(n?1)/2 where n is the length of the list), you'll need to be careful in your data representation: the structure containing the paths will need to use sharing between paths.

Excluding cycles, there is a single path from s to any other node u. If that path goes through an intermediate node t, then the first segment of the path is the desired path from s to t.

I propose to store the result in an array, indexed by nodes numbered from 0 to |E|?1, with s=0. Each element in the array stores the index of the previous node on the path to that node (use e.g. ?1 as a special marker for nodes that are unreachable from s). The path from s to t will be (s=R[

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.