Optimizing Dijkstra for dense graph?

Question

Is there another way to calculate the shortest path for a near complete graph other than Dijkstra? I have about 8,000 nodes and about 18 million edges. I've gone through the thread "a to b on map" and decided to use Dijkstra. I wrote my script in Perl using the Boost::Graph library. But the result isn't what I expected. It took about 10+ minutes to calculate one shortest path using the call $graph->dijkstra_shortest_path($start_node,$end_node);

I understand there are a lot of edges and it may be the reason behind the slow running time. Am I dead in the water? Is there any other way to speed this up?

Answer 1

Do the edges have lengths, or are you just trying to find a path with the minimum number of edges?

10+ minutes is a long time for only 18M edges. Try doing some profiling to see what functions are taking so long.

Answer 2

Short answer: Dijkstra's is your best bet if you want just a few shortest paths, and the Floyd-Warshall algorithm is better if you want to find the shortest paths between every pair of nodes.

• Dijkstra's algorithm finds the shortest paths from one source to all other nodes in the graph, for weighted graphs. It operates on dense graphs in O(V^2) time.

• Floyd-Warshall finds shortest paths between all pairs of nodes. It requires a dense representation and runs in O(V^3) time. It operates on weighted or unweighted graphs.

Even though your graph is dense (according to the title of your question), there might be some benefit to converting it to a sparse graph and using a sparse implementation of Dijkstra's if you just want to find a few shortest paths. Sparse Dijkstra's runs in O(E log V).

Please note that this is assuming that all your edge weights are non-negative; if they are, then you can't use any of these. You would have to use an even slower algorithm, like Bellman-Ford.