Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
3  
Well, if you have a O(V+E) algorithm, I'm really interested! Could you post it here? –  user5974 Mar 9 '11 at 9:22
    
Yes, please do. –  michael.bartnett Apr 8 '12 at 1:17
    
@michael.bartnett: that's kinda old... From what I can remember the idea is to keep reference on each node which node is its shortest path and if that edge changes recalculate that subtree. –  Dani Apr 8 '12 at 11:25
    
I did realize it was old, and I forgot how I got here. But I did really want to know, so I appreciate you giving the gist of it. Thanks! –  michael.bartnett Apr 8 '12 at 12:36
    
If I've understood correctly, the algorithm described by Dani Apr 8 '12 might fail when edge costs are decreased. Imagine we have nodes A,B,C,D,E connected in a pentagon, and our start node S connected to A. Edge CD (furthest from A) costs 1 and the others cost 3 each. Shortest paths to C and D are SABC and SAED respectively (both cost 9). If we decrease the cost of edge BC to 1, the subtree below B is correctly updated (SABC now costs 7), but D is not a member of that subtree. Its path should change to SABCD (new cost 8), but this change is overlooked. Unless I've misunderstood the algorithm. –  DMGregory Mar 23 at 20:07
add comment

4 Answers

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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