johnson#
- johnson(G, weight='weight')[source]#
Uses Johnson’s Algorithm to compute shortest paths.
Johnson’s Algorithm finds a shortest path between each pair of nodes in a weighted graph even if negative weights are present.
- Parameters:
- GNetworkX graph
- weightstring or function
If this is a string, then edge weights will be accessed via the edge attribute with this key (that is, the weight of the edge joining
u
tov
will beG.edges[u, v][weight]
). If no such edge attribute exists, the weight of the edge is assumed to be one.If this is a function, the weight of an edge is the value returned by the function. The function must accept exactly three positional arguments: the two endpoints of an edge and the dictionary of edge attributes for that edge. The function must return a number.
- Returns:
- distancedictionary
Dictionary, keyed by source and target, of shortest paths.
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’s algorithm is suitable even for graphs with negative weights. It works by using the Bellman–Ford algorithm to compute a transformation of the input graph that removes all negative weights, allowing Dijkstra’s algorithm to be used on the transformed graph.
The time complexity of this algorithm is \(O(n^2 \log n + n m)\), where \(n\) is the number of nodes and \(m\) the number of edges in the graph. For dense graphs, this may be faster than the Floyd–Warshall algorithm.
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 theG.nodes
inton
chunks, wheren
is the number of CPU cores.
[Source]