Shortest path in a DAG consisting of multiple copies of a smaller DAG

Question

Let's say we have $k$ weighted DAGs (directed acyclic graphs) $$H_1 = (V_1, A_1), \dots, H_k = (V_k, A_k)$$ that are copies of one another. Now consider another weighted DAG $G$ that is built by combining $H_1, \dots, H_k$ and adding some additional arcs that can only go from one vertex to vertices in the following copies, i.e., consider a weighted DAG $G = (V, A)$ such that:

• $V = \bigcup_{1 \le i \le k} V_i$; and
• $A = ( \bigcup_{1 \le i \le k} A_i ) \cup A'$, such that for each $a = (u, v) \in A'$ we have $u \in V_i, v \in V_j$ with $i < j$.

Now suppose we want to find the shortest $s$-$t$ path for a given pair of vertices $(s, t) \in V^2$. Can precomputing all-pairs shortest paths in $H_1, \dots, H_k$ be used to speed up the algorithm?

Any references to papers that use similar ideas would be helpful.

Answer 1

Yes, you certainly can (based on the fact that any subpath of a minimal path must also be minimal). That is, any shortest path entering $H_i$ at $u$ and leaving at $v$ must follow the shortest path from $u$ to $v$ in $H_i$.

Basically, you can compute the shortest-path distance matrix $D$ for any $H_i$ (it would be the same for all of them, of course), and replace every subgraph $H_i$ by one consisting only of the in- and out-nodes (that is, the nodes connected to other subgraphs; presumably fewer than $|V_i|$), and use only direct edges from the in-nodes to the out-nodes, with weights given by $D$.

You don't need to explicitly construct this new graph, of course. If you have the macrostructure of $G$ available in implicit form, you can compute $D$, and use that together with the macrostructure of $G$ in a (slightly customized) DP algorithm for finding the shortest path.