rustworkx.graph_floyd_warshall#

graph_floyd_warshall(graph, /, weight_fn=None, default_weight=1.0, parallel_threshold=300)#

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

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

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

Parameters:

  • graph (PyGraph) – 运行Floyd算法的图对象

  • weight_fn –

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

    graph_floyd_warshall(graph, weight_fn= lambda x: 1)

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

    graph_floyd_warshall(graph, weight_fn=float)

    将边对象转换为浮点数作为权重。

  • 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