Is All Pairs Shortest Path with PyTorch / CUDA possible?

I don’t know enough about the implementation details to know whether this is a good idea, but would the following be possible / feasible / efficient?

Imagine you have a big graph G = (V, E), and you want to find the shortest path from a to b for all a, b in V. Since this is embarrassingly parallel and has tons of individual threads, is there a known way to use PyTorch/CUDA to find all these paths?

1 Like

In my opinion, it is possible, not feasible, not that efficient.

Textbooks algorithms for all-pairs shortest paths imply that either you use a dynamic programming approach or a particular version of matrix multiplication. https://en.wikipedia.org/wiki/Floyd–Warshall_algorithm

In both cases, you work with matrices/tensors; it is doable with PyTorch.

But you don’t need to calculate gradients or use calculation graphs to solve the problem, that makes it not that feasible and efficient for PyTorch.

One stop library for graph algorithms is Networkx:
https://networkx.github.io/documentation/stable/reference/algorithms/shortest_paths.html

If your graphs don’t fit in memory, take a look at Spark.GraphX: https://spark.apache.org/graphx/ it is specifically designed to distribute the graphs, and work in Pregel-like (message passing) algorithm design.

1 Like