networkx.algorithms.simple_paths.all_simple_paths¶

all_simple_paths(G, source, target, cutoff=None)[source]¶

Generate all simple paths in the graph G from source to target.

A simple path is a path with no repeated nodes.

Parameters:	G (NetworkX graph) source (node) – Starting node for path target (node) – Ending node for path cutoff (integer, optional) – Depth to stop the search. Only paths of length <= cutoff are returned.
Returns:	path_generator – A generator that produces lists of simple paths. If there are no paths between the source and target within the given cutoff the generator produces no output.
Return type:	generator

Examples

This iterator generates lists of nodes:

>>> G = nx.complete_graph(4)
>>> for path in nx.all_simple_paths(G, source=0, target=3):
...     print(path)
...
[0, 1, 2, 3]
[0, 1, 3]
[0, 2, 1, 3]
[0, 2, 3]
[0, 3]

You can generate only those paths that are shorter than a certain length by using the cutoff keyword argument:

>>> paths = nx.all_simple_paths(G, source=0, target=3, cutoff=2)
>>> print(list(paths))
[[0, 1, 3], [0, 2, 3], [0, 3]]

To get each path as the corresponding list of edges, you can use the networkx.utils.pairwise() helper function:

>>> paths = nx.all_simple_paths(G, source=0, target=3)
>>> for path in map(nx.utils.pairwise, paths):
...     print(list(path))
[(0, 1), (1, 2), (2, 3)]
[(0, 1), (1, 3)]
[(0, 2), (2, 1), (1, 3)]
[(0, 2), (2, 3)]
[(0, 3)]

Notes

This algorithm uses a modified depth-first search to generate the paths [1]. A single path can be found in \(O(V+E)\) time but the number of simple paths in a graph can be very large, e.g. \(O(n!)\) in the complete graph of order \(n\).

References

[1]	R. Sedgewick, “Algorithms in C, Part 5: Graph Algorithms”, Addison Wesley Professional, 3rd ed., 2001.