Am 26.10.21 um 16:16 schrieb Monecke, Stephan:
Hi!
I use graph_tool.topology.shortest_distance for an all pairs shortest path calculation, what is the main run-time footprint of my algorithm and way to large.
How would you speed it up / tackle this?
If I knew of a general faster way to solve the all-pairs shortest path problem, I would have implemented it.
I tried to sub-sample with manual source, target pairs but that's terribly inefficient since it does not use the internal bookkeeping.
Nice would be graph_tool.topology.shortest_distance(G, U, V), where U and V are lists of same length with sources / targets but that's not implemented. It is possible to pass a single source but multiple targets.
Subsampling is usually a good technique to reduce the computation time, but it is hard to know what is applicable to you. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>