rustworkx.floyd_warshall#

floyd_warshall(graph, weight_fn=None, default_weight=1.0, parallel_threshold=300)[source]#

使用Floyd算法计算所有节点对之间的最短路径长度

Floyd算法用于在稠密图或带负权重的图中（Dijkstra算法在此类图中会失效）寻找最短路径。

该函数是多线程的，如果图中的节点数超过parallel_threshold的值（默认值为300），默认会启动一个线程数等于CPU数量的线程池。 您可以通过RAYON_NUM_THREADS环境变量来调整线程数量。例如，设置RAYON_NUM_THREADS=4将在启用并行化时将线程池限制为4个线程。

Parameters:

  • graph – 运行Floyd算法的图。可以是PyGraph或PyDiGraph

  • weight_fn (callable) –

    一个可调用对象（函数、lambda表达式等），它将被传递边对象，并预期返回一个float。这告诉rustworkx/rust如何从边对象中提取数值权重作为float。一些简单示例如下：

    floyd_warshall(graph, weight_fn= lambda x: 1)

    为所有边返回权重1。还有：

    floyd_warshall(graph, weight_fn=float)

    将边对象转换为浮点数作为权重。如果未指定此参数，将为所有边使用默认值（default_weight或1）。

  • default_weight (float) – 如果未使用 weight_fn，此参数可 选择性地用于指定所有边的默认权重。

  • parallel_threshold (int) – 执行并行算法时的节点数量阈值。默认设置为300，但可根据需要进行调整

Returns:

一个只读的路径长度字典。键为源节点索引，值为目标节点及其最短路径长度的字典。例如：

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

Return type:

AllPairsPathLengthMapping