Skip to content

Path in a Network

Definition

In the course's terminology, a path is a sequence of distinct edges connecting a starting vertex to an ending vertex, with consecutive edges joined through their shared vertices. For directed edges, traversal respects their directions.

Interpretation

A path describes a route through a network: it starts at one vertex, follows edges that meet end to end, and stops at another vertex. Its length, the sum of the lengths of its edges, is the quantity that route problems compare.

A network of six nodes A to F with edge lengths, with the path A, C, B, D, E, F highlighted; its edges are distinct and its total length is 13.

The highlighted path A−C−B−D−E−FA-C-B-D-E-F uses five different edges, each sharing a vertex with the next, and its length is 2+1+5+2+3=132+1+5+2+3=13.

The course definition requires distinct edges, not distinct vertices. In graph theory such a route is usually called a trail, and path is kept for routes that also visit every vertex at most once; this course uses path for the edge-distinct version. So a route that returns to an earlier vertex is still a path, and one that ends where it starts is a cycle.

Key Results

  • The length of a weighted path is the sum of the lengths of the traversed edges.
  • The course convention corresponds to what some texts call a trail.
  • A path whose first and last vertices coincide is called a cycle or tour in the terminology video.

Examples

The highlighted path is A−C−B−D−E−FA-C-B-D-E-F, with length 2+1+5+2+3=132+1+5+2+3=13.

  • In the course introduction network (not shown here), a path follows A−D−C−E−GA-D-C-E-G.
  • The shortest-path example gives S−B−A−D−E−TS-B-A-D-E-T with length 12.

Prerequisites

Sources

Keywords: trail

Last updated: 20 October 2026 03:02