johnson#

johnson(G, weight='weight')[source]#

使用 Johnson 算法计算最短路径。

Johnson 算法计算加权图中每对节点之间的最短路径，即使图中存在负权边。

参数:
GNetworkX 图
weight字符串或函数

如果这是一个字符串，则通过该键访问边的权重属性（即，连接 u 到 v 的边的权重将是 G.edges[u, v][weight]）。如果不存在这样的边属性，则边的权重假定为 1。

如果这是一个函数，则边的权重是该函数返回的值。该函数必须接受恰好三个位置参数：边的两个端点以及该边的属性字典。该函数必须返回一个数字。

返回:
distance字典

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

另请参阅

floyd_warshall_predecessor_and_distance
floyd_warshall_numpy
all_pairs_shortest_path
all_pairs_shortest_path_length
all_pairs_dijkstra_path
bellman_ford_predecessor_and_distance
all_pairs_bellman_ford_path
all_pairs_bellman_ford_path_length

注意

Johnson 算法甚至适用于存在负权边的图。其工作原理是使用 Bellman-Ford 算法计算输入图的转换，以消除所有负权边，从而允许在转换后的图上使用 Dijkstra 算法。

该算法的时间复杂度是 \(O(n^2 \log n + n m)\)，其中 \(n\) 是节点数，\(m\) 是图中的边数。对于稠密图，这可能比 Floyd–Warshall 算法更快。

示例

>>> graph = nx.DiGraph()
>>> graph.add_weighted_edges_from(
...     [("0", "3", 3), ("0", "1", -5), ("0", "2", 2), ("1", "2", 4), ("2", "3", 1)]
... )
>>> paths = nx.johnson(graph, weight="weight")
>>> paths["0"]["2"]
['0', '1', '2']
----

其他后端实现了此函数

parallel一个使用 joblib 并行运行图算法的 NetworkX 后端。可以在此处找到 nx-parallel 的配置指南。

并行计算是通过将节点分成块，然后并行使用 Johnson 算法计算每个块的最短路径来实现的。

附加参数
get_chunks字符串，函数（默认为 “chunks”）

一个函数，以所有节点的可迭代对象作为输入，并返回一个可迭代对象 node_chunks。默认的分块方式是将 G.nodes 切分成 n_jobs 数量的块。

[源]

本页内容