# Dynamic shortest path data structure for DAG

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

• This seems as though it should be transferred to the (non-research level) Computer Science StackExchange forum. – Niel de Beaudrap Apr 3 '13 at 14:57
• – BlueRaja - Danny Pflughoeft Apr 3 '13 at 16:12
• 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 Apr 4 '13 at 3:33
• 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 Apr 4 '13 at 3:54
• 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 Apr 4 '13 at 7:51