All pairs shortest path lengths for undirected weighted sparse graph

Question

What is the best algorithm for finding the all pairs shortest path lengths for undirected weighted sparse graph? Specifically, the weights are the distances between the nodes (and therefore positive). Note that I only need the path lengths (i.e. not the path itself). My graph is sparse, so it is stored as an adjacency list.

I found Dijkstra, Floyd-Warshall, Johnson, etc. but none of them seem to be optimal for my purpose. In the case of Dijkstra you run the single source version over all vertices, Floyd-Warshall is meant for dense graphs, and Johnson is for directed.

I am specifically looking for an implementation in C++.

Answer 1

Johnson's algorithm seems best suited for sparse graphs (if |V| > |E| it boils down to O(V^2logV), as opposed to O(V^3) with FW). However, since Johnson's algorithm spends the first step on making the weights non-negative (which you don't need), you may run only the second step as you correctly pointed out, which is essentially just Dijkstra from each node. That should take only O(VElogV) as stated here, on the last slide. I'm not sure I can prove it's the best solution, but had there been a better one (for finding shortest paths for non-negative weights) - i'd expect Johnsons algorithm to use it after rewriting the weights.

The fact it works on directed graphs shouldn't bother you - you can convert an undirected graph into a directed one simply by converting each undirected edge with 2 directed edges going back and forth (with a simple O(E) time). That is - unless you have space constraints.

Answer 2

As it is an undirected weighted sparse graph it is very similar to a road network so I don't think (from experience) that there is a better algorithm than Dijkstra. Have a look into bidirectional dijkstra and if you have enough RAM you can cache the shortest path trees (SPT) of every node and then just do the 'matching' between the SPT of point i with the SPT of point j, where i != j.

Answer 3

I haven't tested it, but this paper from 2013 claims to beat Dijkstra by a factor of 47:

Urakov A. R., Timeryaev T. V.: ALL-PAIRS SHORTEST PATHS ALGORITHMFOR HIGH-DIMENSIONAL SPARSE GRAPHS:

The proposed algorithm speeds up the solving of APSP an average of 47 times faster in comparison with the Dijkstra algorithm. For each and all test graphs the algorithm is faster than the Dijkstra’s algorithm (the minimum speed up is 34 times faster). During the tests, the vertices degrees were increased to a maximum of 17. This means that the complexity of the vertices removal increases during the disassembly only slightly.