CODEWITHSUNDEEP
graph-theorydijkstraa-star
Nocta
Nocta

Reputation: 309

Why is A* faster than Dijkstra

I know this question has been asked already but it didn't answer my specific question. I understand how Dijkstra Algorithm and A* Algorithm work and that A* is the general case of Dijkstra.

It is commonly said that A* finds the solution faster which kind of makes sense as you use a heuristic that speeds up the process / reduces the effective branching factor.

But as I recall, to make A* return the optimal result, you have to search ALL nodes that have costs that are less than the costs of the goal. This ensures optimality and also it is said that there can't be an algorithm that is faster, because A* looks at alle nodes <= goal-costs which every algorithm at least has to.

But what about Dijkstra? It also only expends nodes <= goal-costs as it expands the minimal possible path in every step.

What is the A* heuristic good for if you got to expand the other nodes anyway to ensure optimality? Also both algorithms seem to have run-time complexity of n log n

Hope someone can clear this up :)

Upvotes: 1

Views: 4109

Answers (2)

user10982452
user10982452

Reputation:

It's Not. At-least not NECCISARILY. (sorry for late reply)

On a 512x512 Grid with a well written Dijkstra (double loop unrolled) I get less than 1MS search time, by comparison the standard A* with Euclidean distance heuristic takes over 3MS.

This is because A* is very hard to optimize, it involves sorted data and LOTS of dependent branches.

Strictly speaking A* does always expand less nodes than Dijkstra but to say that means therefor means it's 'faster' is a major misunderstanding of how computer algorithms work.

Personally I use an advanced Jump-Point-Search with maintained/updateable precomputed directional cardinal jump maps, this SMASHES A* for number of expanded nodes and work much faster than Dijkstra or A*.

Upvotes: 0

Emisilve86
Emisilve86

Reputation: 354

Dijkstra' Algorithm doesn't use a Heuristic Function to expand the node in the frontier, it looks only for the path that minimizes the cost to reach an unvisited node directly connected to the nodes already visited, it will find the shortest path finally, but would have to explore all the nodes not directly connected to the sink. A* with the help of a good heuristic Function (must be an admissible Heuristic: never overstimates the cost to reach the goal) could reach immediately the sink always expanding the right node in the frontier. So if g(n)=cost to reach node n and h(n)=an admissible heuristic function we get f(n)=g(n)+h(n) the evaluation function used by A*. Instead Dijkstra knows only its frontier and misses the Heuristic information, thus it works as well as A* when heuristic is weak.

Upvotes: 5

Related Questions