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

  • 2
    $\begingroup$ This seems as though it should be transferred to the (non-research level) Computer Science StackExchange forum. $\endgroup$ Commented Apr 3, 2013 at 14:57
  • 1
    $\begingroup$ Possible duplicate of How do the state-of-the-art pathfinding algorithms for changing graphs (D*, D*-Lite, LPA*, etc) differ? $\endgroup$ Commented Apr 3, 2013 at 16:12
  • $\begingroup$ 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.) $\endgroup$
    – Kaveh
    Commented Apr 4, 2013 at 3:33
  • $\begingroup$ 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. $\endgroup$
    – Kaveh
    Commented Apr 4, 2013 at 3:54
  • $\begingroup$ 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. $\endgroup$
    – remo
    Commented Apr 4, 2013 at 7:51


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.