Dynamic Dijkstra

Question

I need dynamic dijkstra algorithm that can update itself when edge's cost is changed without a full recalculation. Full recalculation is not an option.
I've tryed to "brew" my own implemantion with no success. I've also tryed to find on the Internet but found nothing.
A link to an article explaining the algorithm or even it's name will be good.

Edit:
Thanks everyone for answering. I managed to make algorithm of my own that runs in O(V+E) time, if anyone wishes to know the algorithm just say so and I will post it.

Answer 1

Not an answer but might this help? http://www.lix.polytechnique.fr/~liberti/sppsurvey.pdf

Also, a general tip - maybe you already know.

If you know of a paper related to the problem, checking CiteCeer to see if there are papers referencing it, you might find your way to an answer (or not, but always interesting papers on your travels). http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.7969

And lastly, again not an answer - if you get really stuck here's some pointers to possible alternatives: http://www.aiwisdom.com/ai_pathfinding.html

Answer 2

I don't believe that's possible in the general case. You can easily imagine a graph where your source node has only a single connection to the rest of the graph. If that edge changes, the weight of every path from the source will change (although not the paths themselves).

There are other pathological cases you can imagine where even a single edge change would dramatically affect pathing. Imagine a graph with two almost equally weighted chokepoints that almost all paths going to. A slight change in either chokepoint's weight could cause a majority of the paths in the graph to reroute.

If you're willing to settle for an imperfect solution, one option is to have your game constantly recalculating Dijkstra's algorithm incrementally on the graph. So, in addition to your other game processes, you have another loop that works its way through Dijkstra a few nodes every frame, restarting as soon as its done. You can then tune that to spend as much CPU on it per frame as you can afford. You'll get the benefit of running a full recalculation without having the stop the world, the only problem is that you'll have stale paths for a while.

Answer 3

It strikes me that maybe what you want is actually a hidden markov machine so you can treat the true path costs as an unknown and just model them probabilistically? That might be crazy though.

Answer 4

As far as a direct answer, all I have off the top of my head is: A* might help if you can make a good heuristic.

Other ideas: You might be able to do full recalculation over multiple frames (or in a thread). Or maybe try representing your search space in a way that you can use progressive refinement; for example, a quadtree where you can perform a search at coarse granularity (by sum/avg of node costs in that region), then slowly search each subtree.

Of course, if you're working on a very limited platform or very large dataset, that's not going to help. But if that's the case, you probably want a different search algorithm.