Suppose that I would like to find the shortest path between two vertices in a dynamic graph, where the cost function of an edge changes occasionally. I understand that an efficient algorithm to target this problem must have efficient ways to handle the "cost updates" and the shortest path queries.
Does anyone know what is the state-of-the-art method proposed for this problem? And how is the performance like? If you could provide me with a reference as a starting point for my research on this topic, it would be greatly appreciated.
- The weights of the graph do not change while a shortest path computation is carrying on. It is safely to assume that the cost updates of edges happen periodically, like every 15 minutes.