3

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?

Improve this question

2 Answers 2

Reset to default
5

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.

Improve this answer
11
  • 1. Dense, adjaceny matrix. They're pairwise to be exact, but does not quite form a complete graph. 2. Yes, they have positive weight. 3. Ideally all. But at this point I'll be happy to take random samples or as many as I can get. Of the 3 you mentioned Dijkstra fits my problem that best. But the performance doesn't back up the claimed running time. I'm still lost for what could be the bottleneck.
    – user172337
    Commented Sep 12, 2009 at 4:16
  • If your weights can be compressed to 8 or 16 bits with integer representation, perhaps you could save some space and thus time?
    – Greg
    Commented Sep 12, 2009 at 4:28
  • Also, if the graph is undirected, then you should be able to reduce the memory by half by using only the upper triangle of the matrix. I focus on memory here because you might be having problems with data throughput.
    – Greg
    Commented Sep 12, 2009 at 4:30
  • I just implemented Dijkstra on a randomly created matrix-based graph with the same density as your graph. Mine created the graph and ran Dijkstra's algorithm 100 times from different source nodes in 40 seconds. So less than 0.5 seconds per call to Dijkstra. This was C++/Linux/3.0GHz xeon/8GB memory.
    – Greg
    Commented Sep 12, 2009 at 4:44
  • Greg, thanks for trying it out. You're probably correct about the data throughput. My process is showing about 2.4GB of virtual memory on a 2.6GHz Xeon with 16GB. Not too far off from your spec. I'm also starting to suspect Perl is not as efficient as I thought it would be. I choose it mostly for its ease of raw data processing.
    – user172337
    Commented Sep 12, 2009 at 6:26
1

You could also try to give the A* algorithm a spin.

This approach is especially beneficial if you have access to good heuristics.

Improve this answer