[Solved]: Find shortest paths in a weighed unipathic graph

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.