floyd_warshall

floyd_warshall(G, weight='weight')

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

参数:

GNetworkX图

weight: 字符串, 可选 (默认为 'weight')

对应边权重的边数据键。

返回值:

distance字典

一个字典，以源节点和目标节点为键，存储节点间最短路径距离。

另请参阅

floyd_warshall_predecessor_and_distance

floyd_warshall_numpy

all_pairs_shortest_path

all_pairs_shortest_path_length

说明

Floyd算法适用于在密集图或Dijkstra算法失效的带有负权重的图中查找最短路径。如果存在负权环，此算法仍然可能失效。它的运行时间为 \(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)]
... )
>>> fw = nx.floyd_warshall(G, weight="weight")
>>> results = {a: dict(b) for a, b in fw.items()}
>>> print(results)
{0: {0: 0, 1: 5, 2: 7, 3: 4}, 1: {1: 0, 2: 2, 3: -1, 0: inf}, 2: {2: 0, 3: -3, 0: inf, 1: inf}, 3: {3: 0, 2: 8, 0: inf, 1: inf}}
----

其他后端实现了此函数

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