- floyd_warshall_numpy(graph, weight_fn=None, default_weight=1.0, parallel_threshold=300)#
Find all-pairs shortest path lengths using Floyd’s algorithm
Floyd’s algorithm is used for finding shortest paths in dense graphs or graphs with negative weights (where Dijkstra’s algorithm fails).
This function is multithreaded and will launch a pool with threads equal to the number of CPUs by default if the number of nodes in the graph is above the value of
parallel_threshold(it defaults to 300). You can tune the number of threads with the
RAYON_NUM_THREADSenvironment variable. For example, setting
RAYON_NUM_THREADS=4would limit the thread pool to 4 threads if parallelization was enabled.
weight_fn (callable) –
A callable object (function, lambda, etc) which will be passed the edge object and expected to return a
float. This tells rustworkx/rust how to extract a numerical weight as a
floatfor edge object. Some simple examples are:
floyd_warshall_numpy(graph, weight_fn: lambda x: 1)
to return a weight of 1 for all edges. Also:
floyd_warshall_numpy(graph, weight_fn: lambda x: float(x))
to cast the edge object as a float as the weight. If this is not specified a default value (either
default_weightor 1) will be used for all edges.
default_weight (float) – If
weight_fnis not used this can be optionally used to specify a default weight to use for all edges.
parallel_threshold (int) – The number of nodes to execute the algorithm in parallel at. It defaults to 300, but this can be tuned
A matrix of shortest path distances between nodes. If there is no path between two nodes then the corresponding matrix entry will be
- Return type: