NIST

simple path

(definition)

Definition: A path that repeats no vertex, except that the first and last may be the same vertex.

Specialization (... is a kind of me.)
Hamiltonian path, cycle.

See also enumerate all simple paths between two vertices.

Note: In August 2017 the definition changed to allow the first and last vertex to be the same, consistent with Knuth [Knuth98, 1:363]. Before, the definition was "A path that repeats no vertex."

Author: PEB


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 24 August 2017.
HTML page formatted Fri Feb 23 10:06:08 2018.

Cite this as:
Paul E. Black, "simple path", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 24 August 2017. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/simplepath.html