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$.
Asked
Active
Viewed 512 times
4
-
2This seems as though it should be transferred to the (non-research level) Computer Science StackExchange forum. – Niel de Beaudrap Apr 03 '13 at 14:57
-
1Possible duplicate of How do the state-of-the-art pathfinding algorithms for changing graphs (D, D-Lite, LPA*, etc) differ? – BlueRaja - Danny Pflughoeft Apr 03 '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 04 '13 at 03: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 04 '13 at 03: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 04 '13 at 07:51