floyd_warshall_predecessor_and_distance

floyd_warshall_predecessor_and_distance(G, weight='weight')

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

参数

G网络X图表

weight: string, optional (default= 'weight')

与边权重对应的边数据关键点。

返回

predecessor,distance词典

以源和目标为关键字的字典，记录最短路径中的前置任务和距离。

参见

floyd_warshall

floyd_warshall_numpy

all_pairs_shortest_path

all_pairs_shortest_path_length

笔记

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

实例

>>> G = nx.DiGraph()
>>> G.add_weighted_edges_from(
...     [
...         ("s", "u", 10),
...         ("s", "x", 5),
...         ("u", "v", 1),
...         ("u", "x", 2),
...         ("v", "y", 1),
...         ("x", "u", 3),
...         ("x", "v", 5),
...         ("x", "y", 2),
...         ("y", "s", 7),
...         ("y", "v", 6),
...     ]
... )
>>> predecessors, _ = nx.floyd_warshall_predecessor_and_distance(G)
>>> print(nx.reconstruct_path("s", "v", predecessors))
['s', 'x', 'u', 'v']