floyd_warshall_numpy#

floyd_warshall_numpy(G, nodelist=None, weight='weight')[source]#

使用 Floyd 算法查找所有节点对的最短路径长度。

此算法利用图的矩阵表示来查找最短路径，非常适用于需要查找所有节点对最短路径长度的密集图。结果将返回一个 NumPy 数组 distance[i, j]，其中 i 和 j 是 nodelist 中两个节点的索引。distance[i, j] 表示从 i 到 j 的最短路径长度。如果不存在路径，则距离为 Inf。

参数:

GNetworkX 图
nodelist列表，可选 (默认=G.nodes): 行和列的顺序由 nodelist 中的节点确定。如果 nodelist 为 None，则顺序由 G.nodes 产生。nodelist 应包含 G 中的所有节点。
weight: 字符串，可选 (默认=’weight’): 对应于边权重的边数据键。

返回值:

distance二维 numpy.ndarray: 一个表示节点间最短路径距离的 numpy 数组。如果两个节点之间没有路径，则值为 Inf。

引发:

NetworkXError: 如果 nodelist 不是 G 中的节点列表。

说明

当 Dijkstra 算法失效时，Floyd 算法适用于在密集图或带有负权重的图中查找最短路径。如果存在负权环，此算法仍然可能失效。它的运行时间为 \(O(n^3)\)，运行空间为 \(O(n^2)\)。

示例

>>> G = nx.DiGraph()
>>> G.add_weighted_edges_from(
...     [(0, 1, 5), (1, 2, 2), (2, 3, -3), (1, 3, 10), (3, 2, 8)]
... )
>>> nx.floyd_warshall_numpy(G)
array([[ 0.,  5.,  7.,  4.],
       [inf,  0.,  2., -1.],
       [inf, inf,  0., -3.],
       [inf, inf,  8.,  0.]])
----

其他后端实现了此函数

graphblas : 支持 OpenMP 的稀疏线性代数后端。