What data structure should I store my graph in to get the best performance from the Dijkstra algorithm?
Object-pointer? Adjacency list? Something else?
I want the lowest O(). Any other tips are appreciated too!
$\begingroup$
$\endgroup$
asked Feb 24 '13 at 8:46
-
1$\begingroup$ Theoretical interest, or do you want to implement it? If the later, make sure the structures are neatly encapsulated (so you cn change them later), and just write the simplest version that works. If later performance of the system turns out lacking, and measurements show that this is a bottleneck, then you go looking for better/the best. Knuth's "Premature optimization is the root of all evil" is as true a the day it was uttered. $\endgroup$ – vonbrand Feb 24 '13 at 11:30
-
2$\begingroup$ @vonbrand I need to implement it, but I'm not looking to optimize it myself. There are well-known optimal implementations and I want to understand those before I begin so I'm not reinventing the wheel. $\endgroup$ – Barry Fruitman Feb 24 '13 at 18:16
$\begingroup$
$\endgroup$
Implementing Dijkstra's algorithm with a Fibonacci-heap gives $O(|E|+|V|\log |V|)$ time, and is the fastest implementation known.
As for the representation of the graph - theoretically, Dijkstra may scan the entire graph, so an adjacency list should work best, since from every vertex the algorithm scans all its neighbors.
-
$\begingroup$ I read the first part on Wikipedia but I don't understand what to use the heap for. Do you? $\endgroup$ – Barry Fruitman Feb 24 '13 at 9:20
-
$\begingroup$ Wikipedia also says "...making it take only O(log|V|) time instead. The Fibonacci heap improves this to O(|E|+|V|log|V|)." Isn't the second performance WORSE than the first? $\endgroup$ – Barry Fruitman Feb 24 '13 at 9:23
-
1
-
$\begingroup$ BTW this is all related to my other question about Dijkstra's and priority queues. What is the priority queue and/or heap for? Thanks. $\endgroup$ – Barry Fruitman Feb 24 '13 at 9:25
-
$\begingroup$ The priority queue, implemented using a heap, allows you to keep the "frontier" of opened vertices, such that the closest one (w.r.t the distance from $s$) is always at the top. This is equivalent to the standard queue from BFS. $\endgroup$ – Shaull Feb 24 '13 at 9:29
