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']