  Algorithms 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 provide
detailed analysis of parallel APSP performance on distributed memory clusters
with Apache Spark. The Spark model allows for a portable and easy to deploy
distributed implementation, and hence is attractive from the end-user point of
view. We propose four different APSP implementations for large undirected
weighted graphs, which differ in complexity and degree of reliance on
techniques outside of pure Spark API. We demonstrate that Spark is able to
handle APSP problems with over 200,000 vertices on a 1024-core cluster, and can
compete with a naive MPI-based solution. However, our best performing solver
requires auxiliary shared persistent storage, and is over two times slower than
optimized MPI-based solver.
