What graph data structure works fastest with Dijkstra's algorithm?
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.