<p>Let $G$ be a dynamic DAG (directed acyclic graph) where new vertices and new edges can be inserted.</p>

<p>I am looking for an efficient data structure/algorithm to maintain the shortest path from a fixed vertex $s$ to a fixed vertex $t$ in $G$.</p>

CC BY-SA 3.0
2013-04-03T14:57:24.277Z
This seems as though it should be transferred to the (non-research level) [Computer Science StackExchange forum](http://cs.stackexchange.com/questions).
Niel de Beaudrap
CC BY-SA 3.0
2013-04-03T16:12:06.417Z
Possible duplicate of [How do the state-of-the-art pathfinding algorithms for changing graphs (D*, D*-Lite, LPA*, etc) differ?](http://cstheory.stackexchange.com/questions/11855)
BlueRaja - Danny Pflughoeft
CC BY-SA 3.0
2013-04-04T03:33:43.117Z
Does the question linked above answer your question? (It is probably possible to exploit the DAGness and the fact that there are no deletes and $s$ and $t$ are fixed to get better algorithms that those for general case.)
Kaveh
CC BY-SA 3.0
2013-04-04T03:54:23.537Z
In fact, it seems to me that we can have the insert in $O(1)$ and path in time proportional to the size of the path which seems optimal. If you just need to compute the length of the shortest path from $s$ to $t$ then we can probably use a disjoint sets based data structure similar to the one in CLRS pp. 583-584 to get $O(\alpha(n))$ amortized time.
Kaveh
CC BY-SA 3.0
2013-04-04T07:51:14.333Z
Thank you for your comment. The answers above are not exactly about the problem I asked, however they are helpful for me. I fact, I need only "insertNode", "insertEdge" operations. The source and sink are predefined and without any change.
remo
<ds.algorithms><graph-theory><ds.data-structures><directed-acyclic-graph><shortest-path>
Dynamic shortest path data structure for DAG
remo
# Dynamic shortest path data structure for DAG

(Asked by: username_0 on 2013-04-03)

Let $G$ be a dynamic DAG (directed acyclic graph) where new vertices and new edges can be inserted.

I am looking for an efficient data structure/algorithm to maintain the shortest path from a fixed vertex $s$ to a fixed vertex $t$ in $G$.

**Tags:** ds.algorithms, graph-theory, ds.data-structures, directed-acyclic-graph, shortest-path

> **Comments:**
> **username_1**: This seems as though it should be transferred to the (non-research level) [Computer Science StackExchange forum](http://cs.stackexchange.com/questions).  
> **username_2**: Possible duplicate of [How do the state-of-the-art pathfinding algorithms for changing graphs (D*, D*-Lite, LPA*, etc) differ?](http://cstheory.stackexchange.com/questions/11855)  
> **username_3**: Does the question linked above answer your question? (It is probably possible to exploit the DAGness and the fact that there are no deletes and $s$ and $t$ are fixed to get better algorithms that those for general case.)  
> **username_3**: In fact, it seems to me that we can have the insert in $O(1)$ and path in time proportional to the size of the path which seems optimal. If you just need to compute the length of the shortest path from $s$ to $t$ then we can probably use a disjoint sets based data structure similar to the one in CLRS pp. 583-584 to get $O(\alpha(n))$ amortized time.  
> **username_0**: Thank you for your comment. The answers above are not exactly about the problem I asked, however they are helpful for me. I fact, I need only "insertNode", "insertEdge" operations. The source and sink are predefined and without any change.  

---

## 0 answers

