single_source_all_shortest_paths#

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

Compute all shortest simple paths from the given source in the graph.

Parameters:

GNetworkX graph
sourcenode: Starting 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 dictionary: A generator of all paths between source and all nodes in the graph.

Raises:

ValueError: If method is not among the supported options: ‘dijkstra’, ‘bellman-ford’, ‘unweighted’.

See also

shortest_path
all_shortest_paths
single_source_shortest_path
all_pairs_shortest_path
all_pairs_all_shortest_paths

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, 3, 0])
>>> dict(nx.single_source_all_shortest_paths(G, source=0))
{0: [[0]], 1: [[0, 1]], 3: [[0, 3]], 2: [[0, 1, 2], [0, 3, 2]]}