How to calculate the shortest paths between all nodes in Digraph?

[meteorlin]

I think this function is the same as networkx.all_pairs_shortest_path.

[rusty1s]

Yes, you can use networkx for that. Does it work for your use-case?

[meteorlin]

Actually my input graph can be very large (e.g. more than 10,000 nodes), but nx.all_pairs_shortest_path is not implemented in parallel mode, so it is very slow.
My question is specifically:
Given a matrix, each row id represents a node in the directed graph, and each element in the row is the id of other sampled nodes. Now I need to get the depth (that is, the number of hops) of each node in each row relative to the node represented by the current row in the graph.
Specifically, the height of the matrix is the number of all nodes in the graph, and the width is the number of sampled nodes. In other words, although the matrix considers all the nodes in the graph, it only considers their relationship with respect to some other finite number of nodes. So, I wonder if there is a non O(n^2) way to achieve my purpose.

[rusty1s]

I think there exists a lot of fast and alternative libraries to compute shortest paths (I don't think it is solvable in n^2 thought), e.g., cugraph. PyG is not a graph analytics library :(

[meteorlin]

Thanks a lot, I'll look at other ways to reduce the size of the problem.