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。

Parameters:
GNetworkX图
nodelist列表, 可选 (默认=G.nodes)

行和列按nodelist中的节点排序。如果nodelist为None，则按G.nodes生成排序。Nodelist应包含G中的所有节点。

weight: 字符串, 可选 (默认=’weight’)

对应边权重的边数据键。

Returns:
distance2D numpy.ndarray

一个包含节点间最短路径距离的NumPy数组。如果两个节点之间没有路径，则值为Inf。

Raises:
NetworkXError

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

Notes

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

Examples

>>> 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.]])

Additional backends implement this function

graphblas : OpenMP-enabled sparse linear algebra backend.

On this page