Online shortest path in ordered DAG

Question

Suppose I have an edge-weighted connected rooted DAG $G = (V, E, r \in V, w \in E \to \mathbb{Z})$ where there exists a sequence of nonempty sets (called "levels") $L_0 = \{r\}, L_1 \subset V, \ldots, L_n \subset V$ such that $L_0 \cup \ldots \cup L_n = V$ and the outgoing edges of the nodes in $L_i$ only connect to nodes in $L_{i + 1}$.

Is there an online algorithm that can maintain a set of shortest paths as more levels are added to this DAG? In other words, it can answer the query "what is the minimum weight path from the root to some node $n$ in the bottom level of the graph?", even as more levels are added.

I couldn't find any research addressing this question.

Answer 1

If I understand your problem correctly then you probably didn't find any research because the problem is easy to solve.

Unless I missed something, you want to maintain an edge-weighted "layered" DAG $G=(L_0, \cup \dots \cup L_k, E)$ (as defined in your question) and support the following two operations:

• Init(): Create a graph with only one layer $L_0$, a single vertex $r \in L_0$, and no edges.

• Query(): return $\min_{v \in L_k } d(r,v)$.

• Add_Layer($L_{k+1}, E'$): you are given a new set $L_{k+1}$ of vertices and a set of weighted edges $E' \subseteq(L_k \times L_{k+1})$. The vertex set of $G$ is updated to $L_0 \cup \ldots \cup L_k \cup L_{k+1}$ and the edge set of $G$ is updated to $E \cup E'$.

You can do the above by storing: 1) for each vertex $v \in L_k$, the distance $D[v]$ form $s$ to $v$ in $G$, and 2) the minimum distance $d^*$ from $s$ to a vertex of the last level.

The init operation amounts to setting $D[r]=0$. To perform the query operation just return $d^*$.

To implement Add_Layer($L_{k+1}, E'$), you proceed as follows:

• Set $d^*$ to $+\infty$,
• For each vertex $v \in L_{k+1}$:
  • Set $D[v] = +\infty$
  • For each edge $(u,v)$ in $E'$:
    • Update $D[v]$ to $\min\{D[v], D[u] + w(u,v) \}$
  • Update $d^*$ to $\min\{d^*, D[v]\}$

Notice that this requires time proportional to $|L_{k+1}| + |E'|$, and is therefore asymptotically optimal. Notice also that this solution does not need to store $G$.

Answer 2

Suppose you have the length of the shortest paths from the root to all the nodes in level $L_i$, and call this $s \in L_i \to \mathbb{Z}$. Now suppose that the edges from $L_i$ to $L_{i + 1}$ are called $E_i$. Then the length of the shortest path to a node $n$ in $L_{i + 1}$ is defined by $\min \{w(x, n) + s(x) \mid (x, n) \in E_i\}$. Maintaining the actual paths is an easy extension.