Is is possible to implemet all-pairs shortest path algorithm with parallel framework in large graph?

Question

With spark graphx pregel api, it is easy to compute single source shortest path in large graph, for example millions vertices and tens millions edges, with acceptable running time, for example sevral hours. But is it possible to run all-pairs shortest path in large graph in acceptable running time?

Answer 1

Graphs having millions of vertices can be easily processed on single machine, as long as it has sufficient memory, so there is no need to pay the penalty introduced by scaling out and many modern libraries, are heavily optimized and can utilize modern hardware.

In contrast, distributed solutions are usually limited by inter-node communication and exact algorithms just don't scale well. It is possible to improve things significantly with approximations and heuristics and leveraging a priori knowledge about the structure of data.

(Opinion alert) Personally I would steer away as far from possible from graph processing on Spark:

• GraphX has been effectively abandoned few years ago. It also shows very poor scaling capabilities, according to Facebook's study
• Grapframes are immature and inefficient.