Definition: Find all simple paths from a starting vertex (source) to a destination vertex (sink) in a directed graph. In an undirected graph, find all simple paths between two vertices.
See also all pairs shortest path.
Note: The paths may be enumerated with a depth-first search. The search can avoid repeating vertices by marking them as they are visited in the recursion, then removing the mark just before returning from the recursive call.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 2 September 2008.
HTML page formatted Tue May 6 13:48:55 2014.
Cite this as:
Paul E. Black, "all simple paths", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 2 September 2008. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/allSimplePaths.html