2
$\begingroup$

I am using the module networkx to operate on graphs made from OpenStreetMap. I wanted to compare the shortest path algorithm to find which one is faster, and I compared Dijkstra and A*. The problem is : A* is most of the time faster than Dijkstra even though I didn't defined any heuristic function. I understood that A* with $h=0$ was equivalent to Dijkstra, then why is it not the same time?

$\endgroup$
2
$\begingroup$

It depends how you implement Dijkstra. The usual description of Dijkstra adds every vertex of the graph to the queue at the start, which is rather inefficient. A* without a heuristic is often called "uniform cost search" (UCS) and the way it's described, you only add vertices to the queue when you discover them.

This means that, especially in sparse graphs (such as road maps, which are almost planar), UCS has a much lower memory footprint, which can make it considerably faster. Also, the various operations on the queue are much faster, since the queue is typically much shorter.

There's more information in Ariel Felner's paper Dijkstra's algorithm versus uniform cost search or a case against Dijkstra's algorithm (Proceedings of 4th International Symposium on Combinatorial Search, SoCS-2011, AAAI, 2011).

By the way, straight-line distance is probably a very good heuristic for A* in your situation.

$\endgroup$
  • $\begingroup$ Thank you David, this was exatly was I needed ! $\endgroup$ – sophie Jul 10 at 14:09
  • $\begingroup$ Does anyone actually implement it like that outside first year algorithms practicals? $\endgroup$ – Peter Taylor Jul 10 at 23:02
1
$\begingroup$

The best way to answer this is to use a profiler, but since I don't have your test cases I've looked around in the code and I'm fairly confident that it's due to differences in the way they produce the paths.

The networkx A* implementation uses the standard technique of building a predecessor map and chaining backwards down it when the destination is reached. The Dijkstra implementation, on the other hand, produces full lists as it searches. It's wasting a lot of time copying lists to append an element to the end. This is partly a problem of using an inefficient return type, and partly a problem of failing to take advantage of special cases (specifically, using a multi-source multi-destination search to implement single-source single-destination), trading simplicity and non-duplication of code against performance.

$\endgroup$
  • $\begingroup$ Ah, well, if the answer depends on the implementation details of a particular library, then the question isn't really on-topic. $\endgroup$ – David Richerby Jul 11 at 10:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.