1
$\begingroup$

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.
Improve this question
$\endgroup$
2
  • $\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 ♦
    Jan 27, 2017 at 18:51
  • 1
    $\begingroup$ Also, related question. And another one. $\endgroup$
    – Raphael ♦
    Jan 27, 2017 at 18:52

0

Reset to default

Your Answer

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