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