Regarding the query speed of dijkstra and A* algorithm

Question

I am trying to profile the speed of A* and Dijkstra algorithm. I am using the code available at http://www.boost.org/doc/libs/1_38_0/libs/graph/example/astar-cities.cpp and http://www.boost.org/doc/libs/1_50_0/libs/graph/doc/dijkstra_shortest_paths.html. I tried a simple graph with 500 edges and 300 nodes.

I was expecting A* to perform better than Dijkstra since in Dijkstra the shortest distance from the source vertex to every other vertex is found. On the other hand in A* the shortest distance to the goal node is only found.

However, profiling showed that Dijkstra performed slightly better than A*. Is it possible or I am missing something?

Answer 1

Djikstra's algorithm uses a queue while A* uses a priority queue. In general, queues will perform better than priority queues (eg. enqueue/dequeue from a queue using a linked-list or circular-array is O(1), while enqueue/dequeue from a priority queue using a heap is O(log n)).

However, again in general, the cases where this small difference causes A* to run slower than Djikstra's tend to be the cases where both algorithms run extremely fast anyways - in small mazes, and mazes with only a small number of paths to consider (such as a zig-zagging maze). In the slower cases (out in the open with few obstacles), A * should run much faster.

Since your case has 300-nodes, there's a good chance there's something wrong with your code. Without seeing it, we can't help you any further.

Answer 2

Sounds like either your heuristic is inaccurate, or your A* is performing more passes over the data set than Dijkstra (again, perhaps due to the heuristic).

EDIT: For example, if your A* implementation traverses the whole data set and only expands a single node each time (the one with the best heuristic), then it could perform more passes overall than Dijkstra (which expands each node as soon as possible).

If possible, profile the number of passes being performed by each algorithm rather than only looking at the overall processing time.