Editing Path (graph theory) (section)

== Definitions ==
=== Walk, trail, and path ===
[[File:Trail but not path.svg|200px|thumb|right]]
* A '''walk''' is a finite or infinite [[sequence]] of [[Edge (graph theory)|edges]] which joins a sequence of [[Vertex (graph theory)|vertices]].{{sfn|Bender|Williamson|2010|p=162}}
: Let {{nowrap|1=''G'' = (''V'', ''E'', ''Φ'')}} be a graph. A finite walk is a sequence of edges {{nowrap|(''e''<sub>1</sub>, ''e''<sub>2</sub>, ..., ''e''<sub>''n'' − 1</sub>)}} for which there is a sequence of vertices {{nowrap|(''v''<sub>1</sub>, ''v''<sub>2</sub>, ..., ''v''<sub>''n''</sub>)}} such that {{nowrap begin}}''Φ''(''e''<sub>''i''</sub>) = {''v''<sub>''i''</sub>, ''v''<sub>''i'' + 1</sub>}{{nowrap end}} for {{nowrap|1=''i'' = 1, 2, ..., ''n'' − 1}}. {{nowrap|(''v''<sub>1</sub>, ''v''<sub>2</sub>, ..., ''v''<sub>''n''</sub>)}} is the ''vertex sequence'' of the walk. The walk is  ''closed'' if {{nowrap begin}}''v''<sub>1</sub> = ''v''<sub>''n''</sub>{{nowrap end}}, and it is ''open'' otherwise. An infinite walk is a sequence of edges of the same type described here, but with no first or last vertex, and a semi-infinite walk (or [[End (graph theory)|ray]]) has a first vertex but no last vertex.
* A '''trail''' is a walk in which all edges are distinct.{{sfn|Bender|Williamson|2010|p=162}}
* A '''path''' is a trail in which all vertices (and therefore also all edges) are distinct.{{sfn|Bender|Williamson|2010|p=162}}

If {{nowrap|1=''w'' = (''e''<sub>1</sub>, ''e''<sub>2</sub>, ..., ''e''<sub>''n'' − 1</sub>)}} is a finite walk with vertex sequence {{nowrap|(''v''<sub>1</sub>, ''v''<sub>2</sub>, ..., ''v''<sub>''n''</sub>)}} then ''w'' is said to be a ''walk from'' ''v''<sub>1</sub> ''to'' ''v''<sub>''n''</sub>. Similarly for a trail or a path. If there is a finite walk between two ''distinct'' vertices then there is also a finite trail and a finite path between them.

Some authors do not require that all vertices of a path be distinct and instead use the term '''simple path''' to refer to such a path where all vertices are distinct.

A [[weighted graph]] associates a value (''weight'') with every edge in the graph. The ''weight of a walk'' (or trail or path) in a weighted graph is the sum of the weights of the traversed edges. Sometimes the words ''cost'' or ''length'' are used instead of weight.

=== Directed walk, directed trail, and directed path ===
* A '''directed walk''' is a finite or infinite [[sequence]] of [[Edge (graph theory)|edges]] directed in the same direction which joins a sequence of [[Vertex (graph theory)|vertices]].{{sfn|Bender|Williamson|2010|p=162}}
: Let {{nowrap|1=''G'' = (''V'', ''E'', ''Φ'')}} be a directed graph. A finite directed walk is a sequence of edges {{nowrap|(''e''<sub>1</sub>, ''e''<sub>2</sub>, ..., ''e''<sub>''n'' − 1</sub>)}} for which there is a sequence of vertices {{nowrap|(''v''<sub>1</sub>, ''v''<sub>2</sub>, ..., ''v''<sub>''n''</sub>)}} such that {{nowrap|1=''Φ''(''e''<sub>''i''</sub>) = (''v''<sub>''i''</sub>, ''v''<sub>''i'' + 1</sub>)}} for {{nowrap|1=''i'' = 1, 2, ..., ''n'' − 1}}. {{nowrap|(''v''<sub>1</sub>, ''v''<sub>2</sub>, ..., ''v''<sub>''n''</sub>)}} is the ''vertex sequence'' of the directed walk. The directed walk is  ''closed'' if {{nowrap begin}}''v''<sub>1</sub> = ''v''<sub>''n''</sub>{{nowrap end}}, and it is ''open'' otherwise. An infinite directed walk is a sequence of edges of the same type described here, but with no first or last vertex, and a semi-infinite directed walk (or [[End (graph theory)|ray]]) has a first vertex but no last vertex.
* A '''directed trail''' is a directed walk in which all edges are distinct.{{sfn|Bender|Williamson|2010|p=162}}
* A '''directed path''' is a directed trail in which all vertices are distinct.{{sfn|Bender|Williamson|2010|p=162}}

If {{nowrap|1=''w'' = (''e''<sub>1</sub>, ''e''<sub>2</sub>, ..., ''e''<sub>''n'' − 1</sub>)}} is a finite directed walk with vertex sequence {{nowrap|(''v''<sub>1</sub>, ''v''<sub>2</sub>, ..., ''v''<sub>''n''</sub>)}} then ''w'' is said to be a ''walk from'' ''v''<sub>1</sub> ''to'' ''v''<sub>''n''</sub>. Similarly for a directed trail or a path. If there is a finite directed walk between two ''distinct'' vertices then there is also a finite directed trail and a finite directed path between them.

A "simple directed path" is a path where all vertices are distinct. 

A [[Weighted graph|weighted directed graph]] associates a value (''weight'') with every edge in the directed graph. The ''weight of a directed walk'' (or trail or path) in a weighted directed graph is the sum of the weights of the traversed edges. Sometimes the words ''cost'' or ''length'' are used instead of weight.