What are the methods to deal with variations in cost in a dynamic graph when applying Dijkstra? For instance, I select the shortest path in a graph, however, the weight of this path changed after I selected (I made the selection using an estimate). How do I deal with this variation?

  • 2
    $\begingroup$ cs.stackexchange.com/q/7250/755 $\endgroup$
    – D.W.
    Dec 18 '17 at 6:05
  • 1
    $\begingroup$ If edges can change arbitrarily, there's nothing you can other than get all the true weights. But if they are only ever underestimates, or if they only change by a bounded amount (absolute or relative), you may be able to exclude some edges. $\endgroup$ Jan 16 '18 at 16:21

So if I get this right, you computed Dijkstra for your whole graph (that has no negative cycles) and then you are interested in the shortest path between two specific points. You used estimates, and after choosing the shortest (estimated) path, you compute the real path length (you don't do this before for performance reasons I guess).

Now here are my thoughts on this:

  • The real path length will very likely vary from the one you computed using estimates. That's why it is called estimates. So you first have to decide whether you are interested in the definitely shortest path or if it is sufficient to find a most likely or approximately shortest path.
  • For most applications the latter case is sufficient and hence your solution works.
  • If not, you have some possibilities. You could ignore the decreasing performance and just compute Dijkstra with the real values. This would be the easiest solution.
  • The best solution that comes to my mind is:
    1. Estimate the length of all edges
    2. Compute Dijkstra
    3. Find shortest path between the desired nodes
    4. If the shortest path contains one or more estimates: Compute the distances between all nodes along the shortest path and replace the corresponding estimates with your results. Go to 2.
    5. Break; the computed path is indeed the shortest path
  • $\begingroup$ It's not true that the computed path is necessarily the shortest path -- it could be that there is a shorter path (perhaps even a single edge) that was never considered by Dijkstra because its cost estimate is too high. That said, this otherwise seems like a reasonable heuristic. $\endgroup$ Jan 16 '18 at 15:31
  • $\begingroup$ That is true, I didn't even consider that. But I guess if you want the exact values in the end, you need to compute all paths at least partly... $\endgroup$
    – RoyPJ
    Jan 16 '18 at 16:16
  • $\begingroup$ Right, unless you have some kind of guarantee about the relationship between estimates and true values. E.g., if you know that the estimates are always underestimates, your approach will give the correct answer. $\endgroup$ Jan 16 '18 at 16:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.