johnson

johnson(G, weight='weight')

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

Johnson算法可以在一个带有负权重的加权图中找到每对节点之间的最短路径。

Parameters:

GNetworkX图

weight字符串或函数

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

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

Returns:

distance字典

以源节点和目标节点为键的最短路径字典。

See also

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

Notes

Johnson算法适用于带有负权重的图。它通过使用Bellman-Ford算法计算输入图的变换来移除所有负权重，从而允许在变换后的图上使用Dijkstra算法。

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

Examples

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

---

Additional backends implement this function

parallelParallel backend for NetworkX algorithms

The parallel computation is implemented by dividing the nodes into chunks and computing the shortest paths using Johnson’s Algorithm for each chunk in parallel.

Additional parameters:

get_chunksstr, function (default = “chunks”)

A function that takes in an iterable of all the nodes as input and returns an iterable node_chunks. The default chunking is done by slicing the G.nodes into n chunks, where n is the number of CPU cores.

[Source]