rustworkx.digraph_floyd_warshall#

digraph_floyd_warshall(graph, /, weight_fn=None, as_undirected=False, default_weight=1.0, parallel_threshold=300)#

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

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

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

Parameters:

  • graph (PyDiGraph) – 用于运行Floyd算法的有向图

  • weight_fn –

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

    digraph_floyd_warshall(graph, weight_fn= lambda x: 1)

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

    digraph_floyd_warshall(graph, weight_fn=float)

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

  • as_undirected – 如果设为 true，每个有向边将被视为双向/无向边。

  • 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