all_pairs_dijkstra

all_pairs_dijkstra(G, cutoff=None, weight='weight')

查找所有节点之间的最短加权路径和长度。

参数:

GNetworkX 图

cutoff整数或浮点数，可选

搜索停止时的长度（边权重的总和）。如果提供了 cutoff，则只返回总权重小于等于 cutoff 的路径。

weight字符串或函数

如果这是字符串，则通过此键的边属性访问边权重（即，连接 u 和 v 的边的权重将是 G.edge[u][v][weight]）。如果不存在此类边属性，则边的权重假定为 1。

如果这是函数，则边的权重是该函数返回的值。该函数必须精确接受三个位置参数：边的两个端点以及该边的边属性字典。该函数必须返回一个数字或 None 来表示隐藏的边。

生成:

(节点, (距离, 路径))(节点对象, (dict, dict))

每个源节点有两个关联的 dict。第一个按目标节点存储距离，第二个按目标节点存储路径。（有关源/目标节点术语，请参见 single_source_dijkstra。）如果需要，可以将 dict() 应用于此函数，以创建一个以源节点为键，值为这两个 dict 的 dict。

备注

边权重属性必须是数值。距离计算为遍历的加权边的总和。

生成的 dict 只包含可达节点的键。

示例

>>> G = nx.path_graph(5)
>>> len_path = dict(nx.all_pairs_dijkstra(G))
>>> len_path[3][0][1]
2
>>> for node in [0, 1, 2, 3, 4]:
...     print(f"3 - {node}: {len_path[3][0][node]}")
3 - 0: 3
3 - 1: 2
3 - 2: 1
3 - 3: 0
3 - 4: 1
>>> len_path[3][1][1]
[3, 2, 1]
>>> for n, (dist, path) in nx.all_pairs_dijkstra(G):
...     print(path[1])
[0, 1]
[1]
[2, 1]
[3, 2, 1]
[4, 3, 2, 1]
----

其他后端实现了此函数

cugraphGPU 加速后端。

附加参数

dtypedtype 或 None，可选

在算法中用于边权重的数据类型（np.float32, np.float64 或 None）。如果为 None，则 dtype 由边值确定。

parallel一个 NetworkX 后端，使用 joblib 并行运行图算法。在此处查找 nx-parallel 的配置指南 here

并行实现首先将节点划分为块，然后创建一个生成器，以延迟计算每个 node_chunk 的最短路径和长度，然后使用 joblib 的 Parallel 函数在 n_jobs 个 CPU 核心上并行执行这些计算。

附加参数

get_chunks字符串, 函数 (默认值 = “chunks”)

一个函数，接受所有节点的迭代器作为输入，并返回一个 node_chunks 迭代器。默认的分块是通过将 G.nodes 切片为 n_jobs 个块来完成的。

[源]