[ACCEPTED]-What is the fastest Dijkstra implementation you know (in C++)?-algorithm

Accepted answer
Score: 12

The best implementations known for road 5 networks (>1 million nodes) have query times 4 expressed in microseconds. See for more details 3 the 9th DIMACS Implementation Challenge(2006). Note 2 that these are not simply Dijkstra, of course, as 1 the whole point was to get results faster.

Score: 3

May be I am not answering your question. My 12 point is why to use Dijkstra when there 11 are pretty much more efficient algorithms 10 for your problem. If your graph fullfills 9 the triangular property (it is an euclidian 8 graph)

|ab| +|bc| > |ac|

(the distance from 7 node a to node b plus distance from node 6 b to node c is bigger than the distance 5 from node a to node c) then you can apply 4 the A* algorithm. This algorithm is pretty 3 efficient. Otherwise consider using heuristics. The 2 implementation is not the major issue. The 1 algorithm to be used does matter.

Score: 2

Two points I'd like to make: 1) Dijkstra 26 vs A* Dijkstra's algorithm is a dynamic 25 programming algorithm, not an heuristic. A* is 24 an heuristic because it also uses an heuristic 23 function (lets say h(x) ) to "estimate" how 22 close a point x is getting to the end point. This 21 information is exploited in subsequent decisions 20 of which nodes to explore next.

For cases 19 such as an Euclidean graph, then A* works 18 well because the heuristic function is easy 17 to define (one can simply use the Euclidean 16 distance, for example). However, for non 15 Euclidean graphs it may be harder to define 14 the heuristic function, and a wrong definition 13 can lead to a non-optimal path.

Therefore, dijkstra 12 has the advantage over A* which is that 11 it works for any general graph (with the 10 exception of A* being faster in some cases). It 9 could well be that certain implementations 8 use these algorithms interchangeably, resulting 7 in different results.

2) The dijkstra algorithm 6 (and others such as A*) use a priority queue 5 to obtain the next node to explore. A good 4 implementation may use a heap instead of 3 a queue, and an even better one may use 2 a fibonacci heap. This could explain the 1 different run times.

Score: 1

The last time I checked, Dijkstra's Algorithm 7 returns an optimal solution. All "true" implementations 6 of Dijkstra's should return the same result 5 each time.

Similarly, asymptotic analysis 4 shows us that minor optimisations to particular 3 implementations are not going to affect 2 performance significantly as the input size 1 increases.

Score: 0

It's going to depend on a lot of things. How 11 much do you know about your input data? Is 10 it dense, or sparse? That will change which 9 versions of the algorithm are the fastest.

If 8 it's dense, just use a matrix. If its sparse, you 7 might want to look at more efficient data 6 structures for finding the next closest 5 vertex. If you have more information about 4 your data set than just the graph connectivity, then 3 see if a different algorithm would work 2 better like A*.

Problem is, there isn't "one 1 fastest" version of the algorithm.

More Related questions