约翰逊

johnson(G, weight='weight')

使用约翰逊算法计算最短路径。

即使存在负权重，约翰逊算法也会在加权图中找到每对节点之间的最短路径。

参数

G网络X图表

weight字符串或函数

如果这是一个字符串，则边权重将通过具有此关键字的边属性(即边连接的权重)进行访问 u 至 v 将会是 G.edges[u, v][weight] )。如果不存在这样的边属性，则假定边的权重为1。

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

返回

distance词典

以源和目标为关键字的最短路径词典。

加薪

NetworkXError

如果给定的图没有加权。

参见

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

笔记

约翰逊算法甚至适用于负权图。它通过使用Bellman–Ford算法来计算输入图的转换，从而消除所有负权重，从而允许Dijkstra的算法用于转换图。

该算法的时间复杂度为 \(O(n^2 \log n + n m)\) ，在哪里 \(n\) 是节点数和 \(m\) 图形中的边数。对于密集图，这可能比弗洛伊德-沃肖尔算法更快。

实例

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