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
target : node
cutoff : integer, optional
|
---|---|
Returns : | path_generator: generator :
|
See also
shortest_path
Notes
This algorithm uses a modified depth-first search to generate the
paths [R198]. A single path can be found in time but the
number of simple paths in a graph can be very large, e.g.
in
the complete graph of order n.
References
[R198] | (1, 2) R. Sedgewick, “Algorithms in C, Part 5: Graph Algorithms”, Addison Wesley Professional, 3rd ed., 2001. |
Examples
>>> G = nx.path_graph(5)
>>> for path in nx.all_simple_paths(G, source=0, target=4):
... print(path)
[0, 1, 2, 3, 4]
>>> G = nx.Graph()
>>> G.add_path([1,2,3])
>>> G.add_path([1,20,3])
>>> paths = nx.all_simple_paths(G, source=1, target=3)
>>> print(list(paths))
[[1, 2, 3], [1, 20, 3]]