Is there a variant of Dijkstra’s algorithm for partial recalculation?

Question

Suppose the following:

• We use Dijkstra’s algorithm to find the shortest route to our destination.
• The start node (current vehicle position) keeps changing, i.e. moving towards the destination along the calculated shortest path. For this reason we use the inverted form, where the cost of a node represents the cost to reach the destination from there, and the destination’s cost is 0—that way the route graph does not need to change as the vehicle moves through it.
• The cost of edges may change while the vehicle is moving towards the destination (e.g. the traffic situation may affect transit times).
• We want to update the route graph based on edge costs without rebuilding it completely. Rather, as a set of changes arrives, we want to determine which nodes are affected by it and set their cost.
• For now, we are neglecting the fact that the cost of an edge may change again before we reach it—the route is always based on current edge costs.

Is there a standard algorithm for this kind of partial recalculation?

Answer 1

Yes. A search algorithm that is able to quickly recompute the fastest path when small changes are made is known as an incremental algorithm. For your case specifically, you'll want to use D*-Lite, the algorithm used by the Mars Rovers.

See here for more information.

(Note: D*-Lite is decently complex. If this is for a video game, there are better ways to obtain speed-ups using off-the-shelf A* implementations)

Answer 2

The paper linked by BlueRaja - Danny Pflughoeft provided the right pointer, though some effort was required to find a solution for the exact problem above, which I am describing here.

Considerations:

• The existing implementation favors Dijkstra over A*, as we reduce the route graph to a rectangle enclosing the start and destination locations, plus a little extra, and consider local roads only within a certain distance of the start and goal, not within the entire rectangle. (This may give us a non-optimal solution, but that is beyond the scope of this question.) A* comes with the penalty of calculating the heuristic for each node, in exchange for potentially reducing the number of nodes that need to be expanded. In this particular situation, the penalty exceeded the benefit, i.e. A* performs worse than Dijkstra here.
• Dijkstra is equivalent to A* with the heuristic of each node being zero.
• D*-Lite builds upon LPA* (Lifelong Planning A*), which in turn builds upon A*. (Disclosure: I wrote this Wikipedia article yesterday, any errors in there are likely mine.)
• While A* and LPA* are static, D*-Lite incorporates changes of the start node (movement of the vehicle) into the algorithm—which would require architectural changes.

Considering all of the above, a reasonable solution (in terms of achieving the desired result with acceptable performance and without major architectural changes) seems to be:

• Build upon LPA*.
• Calculate from goal to start, unlike canonical Dijkstra/A*/LPA*, but just like the existing algorithm.
• Use a fixed heuristic of zero for all nodes (which the existing routing algorithm effectively does already).

(By the way, if one assumes a fixed start position and a static heuristic of zero, then D*-Lite and LPA* behave identically.)