2
$\begingroup$

I have a nested graph filtration and each step I have to find the shortest path between two nodes. At each step I just add one edge to the graph so the re-computation of the Dijkstra algorithm is extremely redundant. Is there any algorithm to circumvent this?

$\endgroup$
  • $\begingroup$ Please look for "Dynamic Shortest Path" - you'll find a plenty of algorithms $\endgroup$ – HEKTO Oct 16 at 14:17
1
$\begingroup$

Pathfinding algorithms that are able to recompute the best path when the graph changes without doing a full recomputation are called "Incremental".

The incremental version of Dijkstra's algorithm has the horrible name DynamicSWSF-FP.

The much more common algorithm which combines this with A* is called LPA*

$\endgroup$
0
$\begingroup$

You could compute a full Single Source Shortest Paths (SSSP) at the beginning for both of your vertices (s and t).

Then, whenever you add an edge, you update only the shortest paths affected, i. e. you check whether the edge uv provides an improvent for sv, su, tv or tu. If not, your SSSP is still correct. If it gives an improvement, you then also have to check the neighbors for updates. This cascades similarly as the Dijkstra algorithm.

I can't come up with an asymptotic bound right now, but unless the graph and insertion order are chosen adversially, a single edge really shouldnt often invoke a change in large parts of the graph (and when it happens, you have to recompute anyway).

$\endgroup$

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.