rustworkx.digraph_all_pairs_bellman_ford_path_lengths#

digraph_all_pairs_bellman_ford_path_lengths(graph, edge_cost_fn, /)#

For each node in the graph, calculates the lengths of the shortest paths to all others in a PyDiGraph object

This function will calculate the shortest path lengths from all nodes in the graph using the Bellman-Ford algorithm. This function is multithreaded and will launch a thread pool with threads equal to the number of CPUs by default. You can tune the number of threads with the RAYON_NUM_THREADS environment variable. For example, setting RAYON_NUM_THREADS=4 would limit the thread pool to 4 threads.

Parameters:

  • graph – The input PyDiGraph to use

  • edge_cost_fn – A callable object that acts as a weight function for an edge. It will accept a single positional argument, the edge’s weight object and will return a float which will be used to represent the weight/cost of the edge

Returns:

A read-only dictionary of path lengths. The keys are source node indices and the values are dicts of the target node and the length of the shortest path to that node. For example:

{
    0: {1: 2.0, 2: 2.0},
    1: {2: 1.0},
    2: {0: 1.0},
}

Return type:

AllPairsPathLengthMapping

Raises:

NegativeCycle: when there is a negative cycle and the shortest path is not defined.