What graph data structure works fastest with Dijkstra's algorithm?

What data structure should I store my graph in to get the best performance from the Dijkstra algorithm?

I want the lowest O(). Any other tips are appreciated too!

-
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 '13 at 11:30
@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 '13 at 18:16

Implementing Dijkstra's algorithm with a Fibonacci-heap gives $O(|E|+|V|\log |V|)$ time, and is the fastest implementation known.
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 '13 at 9:29