Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 0 down vote favorite

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!

share|improve this question
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. – vonbrand Feb 24 at 11:30
1  
@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. – Barry Fruitman Feb 24 at 18:16

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
I read the first part on Wikipedia but I don't understand what to use the heap for. Do you? – Barry Fruitman Feb 24 at 9:20
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? – Barry Fruitman Feb 24 at 9:23
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. – Shaull Feb 24 at 9:25
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. – Barry Fruitman Feb 24 at 9:25
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. – Shaull Feb 24 at 9:29
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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