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!

Improve this question
$\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 '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
2
$\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.

Improve this answer
$\endgroup$
8
  • $\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$ 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 '13 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$ – 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

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.