Conference PaperSolving All-Pairs Shortest-Paths Problem in Large Graphs Using Apache SparkSchoeneman, Frank; Zola, JaroslawAlgorithms for computing All-Pairs Shortest-Paths (APSP) are critical building blocks underlying many practical applications. The standard sequential algorithms, such as Floyd-Warshall and Johnson, quickly become infeasible for large input graphs, necessitating parallel approaches. In this work, we propose, implement and thoroughly analyse different strategies for APSP on distributed memory clusters with Apache Spark. Our solvers are designed for large undirected weighted graphs, and differ in complexity and degree of reliance on techniques outside of pure Spark API. We demonstrate that the best performing solver is able to handle APSP problems with over 200,000 vertices on a 1024-core cluster. However, it requires auxiliary shared persistent storage to compensate for missing Spark functionality.2019-01-0110145329Proceedings of the 48th International Conference on Parallel Processing1 to 10https://doi.org/10.1145/3337821.33378521910539National Science Foundation