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?