Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

# johnson¶

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

Compute shortest paths between all nodes in a weighted graph using Johnson’s algorithm.

Parameters: G (NetworkX graph) – weight (string, optional (default=’weight’)) – Edge data key corresponding to the edge weight. distance – Dictionary, keyed by source and target, of shortest paths. dictionary NetworkXError – If given graph is not weighted.

Examples

>>> import networkx as nx
>>> 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']


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.

It may be faster than Floyd - Warshall algorithm in sparse graphs. Algorithm complexity: O(V^2 * logV + V * E)

floyd_warshall_predecessor_and_distance(), floyd_warshall_numpy(), all_pairs_shortest_path(), all_pairs_shortest_path_length(), all_pairs_dijkstra_path(), bellman_ford()