Problem Detail: 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!
Asked By : Barry Fruitman
Answered By : Shaull
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/10044
