I understand the basis of A* as being a derivative of Dijkstra, however, I recently found out about D*. From Wikipedia, I can understand the algorithm. What I do not understand is why I would use D* over Dijkstra. To my understanding, Dijkstra gives a best path and D* works backwards from the end goal, but unlike A* it seems to do many calculations, so it doesn't seem as efficient.
Why choose D* over Dijkstra?
algorithms;graphs;search algorithms;efficiency
The main reason for choosing D* is that it is incremental. Basically, when your initial route gets blocked, an incremental search algorithm is able to take advantage of the previous calculations. Dijkstra doesn't do this; it needs to recompute everything from scratch. Such an incremental approach is often used in robotics, navigation, and planning.This is the short answer. For much more, I think you would be interested in How do the state-of-the-art pathfinding algorithms for changing graphs (D*, D*-Lite, LPA*, etc) differ?