Finding all shortest paths from every pair of nodes on a graph

Question

I have about 70k nodes, and 250k edges, and the graph isn't necessarily connected. Obviously using an efficient algorithm is crucial. What do you recommend?

As a side note, I would appreciate advice on how to divide the task up between several machines--is that even possible with this kind of problem?

Thanks

Answer 1

You could use the Floyd-Warshall algorithm. It solves exactly this problem.

The complexity is O(V^3).

There is also Johnson's algorithm with a complexity of O(V^2*log V + VE). The latter is also easy to distribute because it runs Dijkstra's algorithm V times, which can be done in parallel.