Difference and advantages between dijkstra & A star [duplicate]

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.

Solution 1:

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).

Solution 2:

Dijkstra is a special case for A* (when the heuristics is zero).

A* search:

It has two cost function.

g(n): same as Dijkstra. The real cost to reach a node n.
h(n): approximate cost from node n to goal node. It is a heuristic function. This heuristic function should never overestimate the cost. That means, the real cost to reach goal node from node n should be greater than or equal h(n). It is called admissible heuristic.

The total cost of each node is calculated by f(n)=g(n)+h(n)

Dijkstra's:

It has one cost function, which is real cost value from source to each node: f(n)=g(n) It finds the shortest path from source to every other node by considering only real cost.