<p>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$ <em>must</em> follow the shortest path from $u$ to $v$ in $H_i$.</p>

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

<p>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.</p>

CC BY-SA 3.0
2011-12-21T19:48:44.210Z
The question was interesting and the answer seems absolutely right to me. Why did not anybody wanted to vote it up? Good answer Magnus!
Carlos Linares López
CC BY-SA 3.0
2011-07-15T09:31:22.857Z
2011-07-15T09:31:22.857Z
Magnus Lie Hetland
<p>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:</p>

<ul>
<li>$V = \bigcup_{1 \le i \le k} V_i$; and</li>
<li>$A = ( \bigcup_{1 \le i \le k} A_i ) \cup A&#39;$, such that for each $a = (u, v) \in A&#39;$ we have $u \in V_i, v \in V_j$ with $i &lt; j$.</li>
</ul>

<p>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?</p>

<p>Any references to papers that use similar ideas would be helpful.</p>

<ds.algorithms><graph-algorithms><directed-acyclic-graph>
Shortest path in a DAG consisting of multiple copies of a smaller DAG
Caleb Poucher
# Shortest path in a DAG consisting of multiple copies of a smaller DAG

(Asked by: username_0 on 2011-07-14)

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.

**Tags:** ds.algorithms, graph-algorithms, directed-acyclic-graph

---

## 1 answers

### Answer by username_1 on 2011-07-15. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_2**: The question was interesting and the answer seems absolutely right to me. Why did not anybody wanted to vote it up? Good answer Magnus!  

---

