all_pairs_all_shortest_paths#

all_pairs_all_shortest_paths(G, weight=None, method='dijkstra')[source]#

Compute all shortest paths between all nodes.

Parameters:

GNetworkX graph
weightNone, string or function, optional (default = None): If None, every edge has weight/distance/cost 1. If a string, use this edge attribute as the edge weight. Any edge attribute not present defaults to 1. 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.
methodstring, optional (default = ‘dijkstra’): The algorithm to use to compute the path lengths. Supported options: ‘dijkstra’, ‘bellman-ford’. Other inputs produce a ValueError. If weight is None, unweighted graph methods are used, and this suggestion is ignored.

Returns:

pathsgenerator of dictionary: Dictionary of arrays, keyed by source and target, of all shortest paths.

Raises:

ValueError: If method is not among the supported options.

See also

all_pairs_shortest_path
single_source_all_shortest_paths

Notes

There may be multiple shortest paths with equal lengths. Unlike all_pairs_shortest_path, this method returns all shortest paths.

Examples

>>> G = nx.cycle_graph(4)
>>> dict(nx.all_pairs_all_shortest_paths(G))[0][2]
[[0, 1, 2], [0, 3, 2]]
>>> dict(nx.all_pairs_all_shortest_paths(G))[0][3]
[[0, 3]]

Additional backends implement this function

parallelParallel backend for NetworkX algorithms

The parallel implementation first divides the nodes into chunks and then creates a generator to lazily compute all shortest paths between all nodes for each node in node_chunk, and then employs joblib’s Parallel function to execute these computations in parallel across all available CPU cores.

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]