3
$\begingroup$

I have an acyclic edge-weighted graph and have used Dijkstra's Algorithm with topological sort to find any shortest path to every other node from a root $s$. This is performed in time proportional to $V + E$, where $V$ is the number of vertices and $E$ the number of edges. I have $V= N^2$ vertices in my graph. Now suppose I remove $N$ vertices (for now lets assume at random, in reality there is a pattern). If I want to find shortest paths for my new graph, is there any information from the first computation that I can cache to speed things up?

$\endgroup$
  • $\begingroup$ The claim you make in your second sentence doesn't seem like it can be correct. You can't enumerate all shortest paths from a root to $s$ in $O(|V|+|E|)$ time, as there can be exponentially many shortest paths. So what do you really mean? See e.g. cs.stackexchange.com/q/25842/755 and cs.stackexchange.com/q/38000/755. $\endgroup$ – D.W. Feb 27 '15 at 22:15
  • $\begingroup$ @D.W. I am happy to accept any shortest path when there are multiple shortest paths. $\endgroup$ – Dilitante Mar 4 '15 at 17:13
  • $\begingroup$ OK. I encourage you to edit the question accordingly, in that case. $\endgroup$ – D.W. Mar 4 '15 at 19:05
3
$\begingroup$

A simple approach

Given that you have a DAG, and the only change you will make is to delete vertices, there is a crude but simple to implement algorithm you could use. In addition to computing the distance from $s$ to every vertex, also compute the shortest paths tree.

Now, when you want to delete a vertex $v$, mark the entire subtree rooted at $v$ (in the shortest path tree). Delete this from the shortest path tree, and process each of the nodes in that subtree to re-calculate their distance from $s$. You can process those vertices in topological sorted order, and compute the updated distance for vertex $x$ by the standard formula $d(x) = \min \{1+d(w) : (w,x) \in E\}$. The running time will be proportional to the size of the subtree you deleted. Whether this is efficient in practice will depend on the structure of the graph and the nodes that you delete.

More sophisticated solutions

This kind of problem has been studied extensively in the literature. The keyword you want to use is "dynamic shortest paths". Here dynamic refers to the fact that the graph can change. In your case, you want to support vertex deletions. So, I suggest you spend some quality time with the research literature to review the known algorithms for dynamic shortest paths with vertex deletions. Alternatively, look for algorithms for dynamic shortest paths with edge deletions (since when you delete a vertex you're probably going to delete all edges incident on that vertex as well).

See, e.g., Retrieving the shortest path of a dynamic graph and How to approach Dynamic graph related problems and https://cstheory.stackexchange.com/q/17135/5038 and https://cstheory.stackexchange.com/q/11855/5038 for some entry points into the literature. Those algorithms apply to arbitrary graphs, but it might be possible to exploit the fact that your graph is actually a DAG to get even better performance.

$\endgroup$
  • $\begingroup$ Thanks for the links, I've spent the last few days reading. I should have said before I am actually interested in an edge weighted DAG and I need to handle edge insertions and deletions (i.e. fully dynamic). The closest thing I have found so far is a $O(log^4(n)$ fully dynamic algorithm for an unweighted DAG. I am working on understanding this better in the hope that I can adapt it accordingly for the edge weighted case. $\endgroup$ – Dilitante Mar 4 '15 at 17:11
  • $\begingroup$ @JamesGallagher, OK. That radically changes the question. You might want to look through the literature on fully dynamic shortest paths, then post a new question that matches what you're looking for, and show us in that question what the best algorithm you've found is. There's tons of literature on this problem and I don't know what the best algorithm is for the special case where the graph is known to be a DAG. (And in the future make sure to ask the question you care about; these details can change the answer tremendously.) $\endgroup$ – D.W. Mar 4 '15 at 19:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.