Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question
1  
What have you tried so far? If you are totally stuck, start small: what do unipathic graphs really look like? For example, draw every unipathic graph with one vertex, two vertices, three vertices, and so on. You might spot a helpful pattern. In addition, you mention there are no negative weight cycles - can there even be cycles (of any weight)? –  Juho Mar 21 '12 at 20:26
    
@mrm What pattern are you thinking of? Unipathic graphs can have cycles, in a constrained way that I can't find an easy way to express. –  Gilles Mar 22 '12 at 14:57
    
@mrm No. An edge can belong to at most one cycle. A node can belong to any number of cycles: the $n$-pointed-star-shaped graph $E=\bigcup_{i\le n} \{(a,b_i),(b_i,a)\}$ is unipathic (and you can get an even higher ratio of elementary cycles per node). –  Gilles Mar 22 '12 at 16:06

1 Answer 1

up vote 10 down vote accepted

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[\ldots R[t]\ldots],\ldots,R[R[t]],R[t],t)$.

Traverse the graph

Initialize $R$ to all $-1$.

Perform a depth-first or breadth-first traversal of the graph starting from $s$. Each time a node $u$ is reached, set $R[u]$ to its predecessor.

Since there are cycles, a node might be reached more than once. Having $R[u] \ne -1$ indicates that $u$ has already been visited.

Prove the correctness

Because of the unipathic property, it doesn't matter how we reach each node, as long as we haven't completed a cycle. There is only one simple path.

Prove the complexity

The algorithm may reach each node more than once, so it's not clear that its complexity is $O(|V|)$. The work done is in fact $\Theta(|E_0|)$ where $V_0$ are the edges that are reachable from the source. More precisely, we reach a node more than once only in one circumstance: if the node is the first that we reach on a particular cycle, and in this case we reach it twice (once from a simple path, and once after completing the cycle).

Well then. Let's prove that in a unipathic graph, the number of elementary cycles grows at most linearly with the number of nodes. (An elementary cycle is one that does not contain a shorter cycle.) In the following discussion, I'll assume that the graph has no self-edge (no edge from a node to itself; such edges are irrelevant for the path construction anyway).

Unipathic graphs can have cycles, but in a very constrained way. It would be nice if we could somehow associate each cycle to a distinct node (or at least, at most a bounded number of cycles per node). Can cycles share a node? Unfortunately, yes.

You can have $m$ cycles all sharing one node $a$ and no other nodes. The resulting graph is unipathic. With cycles of length 2, this is a star pattern with a central node $a$ and any number of nodes $b_i$ such that $\forall i, a \leftrightarrows b_i$.

So we'll need to work harder. Well, let's try to prove it inductively. Let $\#V(G)$ be the number of nodes in a graph $G$, $\#E(G)$ the number of edges and $\#C(G)$ the number of elementary cycles that aren't self edges. I assert that if $G$ is unipathic and not empty then $\#C(G) \le \#V(G)-1$.

For a graph with one or two nodes, this is obvious. Suppose the assertion holds for all graphs such that $\#V(G) < n$ and let $G$ be a unipathic graph with $n$ nodes. If $G$ has no cycle, $0 = \#C(G) < \#V(G)$, case closed. Otherwise, let $(a_1,\ldots,a_m)$ be an elementary cycle.

Collapse the cycle: let $G'$ be the graph whose nodes are those of $G$ minus $\{a_1,\ldots,a_m\}$ plus a node $a$ and whose edges are all the edges of $G$ not involving the $a_i$'s, plus $a \rightarrow_{G'} b$ whenever $\exists i, a_i \rightarrow_G b$ and $b \rightarrow_{G'} a$ whenever $\exists i, b \rightarrow_G a_i$. Every path in $G'$ induces a path in $G$ (if the path involves $b \rightarrow a \rightarrow c$, then replace this by $b \rightarrow a_i \rightarrow a_{i+1} \rightarrow \ldots \rightarrow a_j \rightarrow c$ in $G$). Therefore $G'$ is unipathic. Furthermore, since cycles in $G$ do not share edges, $G'$ has all the cycles in $G$ except for the one we eliminated: $\#C(G') = \#C(G)-1$. By induction, $\#C(G') \le \#V(G')-1$. Since $\#V(G') = \#V(G) - m + 1$, we have $\#C(G) = \#C(G')+1 \le \#V(G) - m = n-m \le n-1$.

This concludes the proof. The traversal follows at most $2|V|-2$ edges.

share|improve this answer
    
Thanks, this was extremely helpful –  gprime Mar 23 '12 at 21:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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