CODEWITHSUNDEEP
algorithmgraph-algorithmdijkstrashortest-path
excalibur1491
excalibur1491

Reputation: 1221

Incremental Dijkstra or shortest path algorithm?

I have an initial directed graph G, from which I remove edges from time to time (never add new ones). I don't remove nodes (although some might end up disconnected). Is there a way to efficiently recompute shortest paths without running Dijkstra from scratch again? The initial node never changes.

If there is no incremental version of Dijkstra's algorithm, some other algorithm would be fine. But I can't use A* (I recall there is an incremental version of it) because I have no heuristic whatsoever to know how far I am from a destination.

Thank you

Upvotes: 4

Views: 1448

Answers (1)

Sorin
Sorin

Reputation: 11968

You can keep track of the edges used. If you remove one then you can use them to find all the nodes that need to be updated.

The rest of the nodes don't need to be updated. If you remove edges you can only make paths longer.

Run through all the edges and if the source doesn't need an update but the destination does add the destination to the Dijkstra priority queue. Once you've done that run the regular Dijkstra algorithm to figure out the new costs.

That being said you might still run the entire dijkstra if you remove one of the links from the source. So probably this is only useful if you don't try to remove used links (as in there's a good chance that the link removed is not used anyway) or if you remove link so that it's far away from source (that way you only need to update a few nodes).

Upvotes: 1

Related Questions