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.
  • $\begingroup$ Since many distances can change, I don't think you can do better than just re-running your SSSPP algorithm of choice in the worst case. Also, just to be clear: are the weights changing while the algorithm runs, or do you want to maintain distances over time while weights change? $\endgroup$
    – Raphael
    Commented Jan 27, 2017 at 18:51
  • 2
    $\begingroup$ Also, related question. And another one. $\endgroup$
    – Raphael
    Commented Jan 27, 2017 at 18:52


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.