Note

This documents the development version of NetworkX. Documentation for the current release can be found here.

# networkx.algorithms.shortest_paths.weighted.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
• G (NetworkX graph)

• weight (string 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 to v will be G.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

distance – Dictionary, keyed by source and target, of shortest paths.

Return type

dictionary

Raises

NetworkXError – If given graph is not weighted.

Examples

>>> graph = nx.DiGraph()
...     [("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']


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.

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()