  The Floyd-Warshall(FW) algorithm, is an ancient but a largely important
algorithm used to solve the all-pairs simple-paths(APSP) problem. While the
algorithm is available for use in open-source graph optimization libraries such
as NetworkX, they do not take advantage of modern parallel processing hardware
such as Graphics Processing Units(GPUs), which would reduce compute time to a
fraction of its iterative or recursive implementations. In this work, a
re-implementation of the Floyd-Warshall algorithm using open-source GPU
libraries such as PyTorch is presented. A further implementation of the
R-Kleene is also described, a slightly newer algorithm used for solving the
APSP problem in a divide-and-conquer, recursive but highly parallelized
architecture. In addition, a random graph generator that generates a wide range
of graphs of different scales is also contributed, where the densities and
connectivities are controlled using some heuristics. The run-times of the GPU
accelerated FW algorithm and R-Kleene on these heuristically generated graphs
are evaluated against each other and to the widely used implementation from
NetworkX. The code for the GPU implementation of the algorithms, the random
graph generator, and the Blender animation file are available at
https://github.com/tanjary21/APSP_GPU/.

Distributed, Parallel, and Cluster Computing