3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The question was interesting and the answer seems absolutely right to me. Why did not anybody wanted to vote it up? Good answer Magnus! $\endgroup$ – Carlos Linares López Dec 21 '11 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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