Comparison of routing algorithms for pedestrian navigation [closed]

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance. Closed 10 years ago.

I'm currently working on software for pedestrian navigation and the topic that is hard for me is to find the routing algorithm best suited for that task. I heard that A* is one of the algorithms actually used in that kind of software.

Could you suggest other algorithms that solve this problem? How do they compare regardi开发者_StackOverflowng performances? How much memory and space do they require?

Thanks in advance for answers.

---

Well you could have a look at iterative deepening search. It's a very smart approach to your problem in my opinion, but you risk to have a quite bad time complexity with respect to A* with a good heuristic since the algorithm is designed to make a complete exploration.

From wikipedia:

IDDFS combines depth-first search's space-efficiency and breadth-first search's completeness (when the branching factor is finite). It is optimal when the path cost is a non-decreasing function of the depth of the node. The space complexity of IDDFS is O(bd), where b is the branching factor and d is the depth of shallowest goal. Since iterative deepening visits states multiple times, it may seem wasteful, but it turns out to be not so costly, since in a tree most of the nodes are in the bottom level, so it does not matter much if the upper levels are visited multiple times.

And again, for what concerns time complexity:

The time complexity of IDDFS in well-balanced trees works out to be the same as Depth-first search: O(bd).