Find shortest paths in a weighed unipathic graph

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

Answer 1

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.