The large network (of small world graph type) I wish to deal with is dynamic in nature, new nodes are added and subtracted frequently. Presumably using D* over A* would be a better way to detect paths in this dynamic environment?
How solid is D*? has it had any real world experience? like a cryptographic algorithm - is D* hardened by lots of peer review and testing? Would you use D* for this problem?
As I understand, the first time you run D* it finds the same path as A* with nearly the same runtime. However, when a node changes it's edge value or nodes are added A* recomputes ALL of the path while D* simply recomputes the inconsistent nodes the second time around rather than the whole thing.
Anthony Stentz's D* algorithm (original whitepaper here) has largely been deprecated by derivatives of his work. D* Lite and LPA* are the most commonly found and are much easier to code/implement.
As far as real world experience, Joseph Carsten and Art Rankin from NASA's Jet Propulsion Laboratory installed a version of Field D* using elements of D* Lite on the mars rovers "Spirit" and "Opportunity" (slideshow of rovers using D* here). In Feburary 2007 it was used to fully navigate the mars rover autonomously.
alt text http://asm.arc.nasa.gov/Gallery/images/generic/rover.jpg
Apparently D* is really useful in the robotics domain because the robots on-board sensors are constantly re-evaluating edge values. That would make it pretty "battle tested" in my own opinion.
Similarly, I found another whitepaper that mentions the use of the D* Lite algorithm in Mobile Gaming.
I'll end this answer by stating that I've never implemented D* before, only A*. Because of the significant increase in complexity I would say that D* (or D* Lite) should only be used in cases where there is a significant and frequent changes in the graph. You described your situation as being similar to that so I would say definately go for D* Lite. If NASA uses it you could safely bet it has been thoroughly investigated.
I have implemented both D* and A* algorithm. So, I advice you that, if your map has no dynamic obstacles, you should implement A*. Else, implement D*. For the main reason is: At the first search, D* calculates all nodes in the map, then shows you the shortest path, while A* only calculates a limited area around goal and start points in the map. So, it is much faster than D*. In dynamic environment, D* is faster and more efficient than A*. Because on the way robot goes, if it detects a new obstacle, it only updates a few nodes around the unexpected obstacle. While, A* will calculates again all things.
