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!
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityWhat 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!
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.