0
$\begingroup$

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!

$\endgroup$
2
  • 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, 2013 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$ Feb 24, 2013 at 18:16

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ I read the first part on Wikipedia but I don't understand what to use the heap for. Do you? $\endgroup$ Feb 24, 2013 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$ Feb 24, 2013 at 9:23
  • 2
    $\begingroup$ Read chapters 20 and 24 in CLRS. They explain how to implement the Fibonacci heap. After that, you just use this heap as the priority queue. $\endgroup$
    – Shaull
    Feb 24, 2013 at 9:25
  • $\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$ Feb 24, 2013 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, 2013 at 9:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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