floyd_warshall

floyd_warshall(G, weight='weight')

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

Parameters:

GNetworkX图

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

对应边权重的边数据键。

Returns:

distance字典

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

See also

floyd_warshall_predecessor_and_distance

floyd_warshall_numpy

all_pairs_shortest_path

all_pairs_shortest_path_length

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

---

Additional backends implement this function

graphblas : OpenMP-enabled sparse linear algebra backend.