Running AStar on an updating graph

Question

We are working on a project which involves running a shortest path algorithm on a big map.

We are using AStar with the Air Distance heaurstic for now.

Our project involves receiving updates to links in the database. Currently we restart the search for each link update or at every predefined interval. Is there a way to update the AStar algorithm to update the search without restarting the search on every update received? Is there a better algorithm suited for this task?

Disclosure: This is part of students project.

Thank you.

Answer 1

You might be looking for a routing algorithm (that by nature deals with constantly changing graphs).

One way to achieve it is with Distance Vector Routing Protocol (which is a distributed version of Bellman Ford algorithm) and works as follows¹:

• periodically, every vertex sends its "distances vector" to its neighbors [the vector indicates how much it 'costs' to travel from the sending vertex, to each other vertex.
• Its neighbors try to update their routing tables [through which edge is it best to move to the each target]
• for your case, each node knows what is the fastest way to get to its neighbors (1 if the graph is unweighted) and it (the vertex) adds this number to each entree in the distance vector, in order to know how to and how much time it will take, to get to the destination. Every time a modification arrives, the relevant node will invoke a new iteration of the protocol until it re-converges.

Note however, that this algorithm is uninformed (but deals well with changing graphs, with certain limitations, there is still the count to infinity problem)

---

(1) The explanation of the algorithm is based on an explanation I provided some time back in this thread, with some modifications. (It is the same suggested algorithm after all).