Difference and advantages between dijkstra & A star
I read this: http://en.wikipedia.org/wiki/A*_search_algorithm
It says A* is faster than using dijkstra and uses best-first-search to speed things up.
If I need the algorithm to run in milliseconds, when does A* become the most prominent choice.
From what I understand it does not necessarily return the best results.
If I need quick results, is it better to pre-compute the paths? It may take megabytes of space to store them.
Answer
It says A* is faster than using dijkstra and uses best-first-search to speed things up.
A* is basically an informed variation of Dijkstra.
A* is considered a "best first search" because it greedily chooses which vertex to explore next, according to the value of f(v) [f(v) = h(v) + g(v)] - where h is the heuristic and g is the cost so far.
Note that if you use a non informative heuristic function: h(v) = 0 for each v: you get that A* chooses which vertex to develop next according to the "so far cost" (g(v)) only, same as Dijkstra's algorithm - so if h(v) = 0, A* defaults to Dijkstra's Algorithm.
If I need the algorithm to run in milliseconds, when does A* become the most prominent choice.
Not quite, it depends on a lot of things. If you have a descent heuristic function - from my personal experience, greedy best first (choosing according to the heuristic function alone) - is usually significantly faster than A* (but is not even near optimal).
From what I understand it does not necessarily return the best results.
A* is both complete (finds a path if one exists) and optimal (always finds the shortest path) if you use an Admissible heuristic function. If your function is not admissible - all bets are off.
If I need quick results, is it better to pre-compute the paths? It may take megabytes of space to store them.
This is a common optimization done on some problems, for example on the 15-puzzle problem, but it is more advanced. A path from point A to point B is called a Macro. Some paths are very useful and should be remembered. A Machine Learning component is added to the algorithm in order to speed things up by remembering these Macros.
Note that the path from point A to point B in here is usually not on the states graph - but in the problem itself (for example, how to move a square from the lowest line to the upper line...)
To speed things up:
If you have a heuristic and you find it too slow, and you want a quicker solution, even if not optimal - A* Epsilon is usually faster then A*, while giving you a bound on the optimality of the path (how close it is to being optimal).