all_shortest_paths#

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

Compute all shortest simple paths in the graph.

Parameters:

GNetworkX graph
sourcenode: Starting node for path.
targetnode: Ending node for path.
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’, ‘unweighted’. Other inputs produce a ValueError. If method='unweighted' is passed explicitly, the search treats every edge as having equal weight, and the weight argument, if given, is ignored. If weight is None, unweighted graph methods are used regardless of what method is set to.

Returns:

pathsgenerator of lists: A generator of all paths between source and target.

Raises:

ValueError: If method is not among the supported options: ‘dijkstra’, ‘bellman-ford’, ‘unweighted’.
NetworkXNoPath: If target cannot be reached from source.

See also

shortest_path
single_source_shortest_path
all_pairs_shortest_path

Notes

There may be many shortest paths between the source and target. If G contains zero-weight cycles, this function will not produce all shortest paths because doing so would produce infinitely many paths of unbounded length – instead, we only produce the shortest simple paths.

Examples

>>> G = nx.Graph()
>>> nx.add_path(G, [0, 1, 2])
>>> nx.add_path(G, [0, 10, 2])
>>> print([p for p in nx.all_shortest_paths(G, source=0, target=2)])
[[0, 1, 2], [0, 10, 2]]