Paths

Definition

A path in a graph is a sequence of vertices in which each consecutive pair of vertices is joined by an edge.

If the vertices are written as
$$v_0, v_1, v_2, \dots, v_k$$ then this sequence is a path if every edge
$$(v_{i-1}, v_i)$$ exists in the graph for all $i = 1, 2, \dots, k$.

A path may be:

Simple path

• : no vertex is repeated.

Walk

• : vertices and edges may repeat.

Trail

• : edges are not repeated, but vertices may repeat.

Closed path

• : the starting and ending vertex are the same.

Cycle

• : a closed simple path, where no vertex repeats except the first and last.

Example:

If a graph has edges $A-B$, $B-C$, and $C-D$, then
$$A \to B \to C \to D$$ is a path of length 3.

---

Main Content

1. Types of Paths

Simple path

• : A path in which all vertices are distinct. This is the most commonly studied type because it avoids repetition and gives a clean route from one vertex to another.

Closed path and cycle

• : If the path starts and ends at the same vertex, it is closed. If, in addition, no other vertex is repeated, it becomes a cycle. Cycles are especially important in detecting loops in graphs.

Directed and undirected paths

• : In an undirected graph, edges can be used in either direction, so traversal is flexible. In a directed graph, the direction of every edge must be respected, so a path can exist in one direction but not the reverse.

Example:

Undirected graph:
$A - B - C - D$

Possible path:
$A \to B \to C \to D$

Directed graph:
$A \to B \to C$

Here $A \to C$ is a path through $B$, but $C \to A$ is not a path unless reverse edges exist.

2. Length and Cost of a Path

Length of a path

• : The length is the number of edges in the path. For example, $A \to B \to C \to D$ has length 3.

Weighted graphs

• : In weighted graphs, each edge has a value such as distance, cost, time, or capacity. The total path cost is the sum of the weights of all edges in the path.

Shortest path idea

• : Among all possible paths between two vertices, the one with the minimum total cost is called the shortest path. This is one of the most important applications of path theory.

Example:

If
$A-B = 4$, $B-C = 2$, and $A-C = 10$, then:

• Path $A \to B \to C$ has total cost $4 + 2 = 6$
• Direct path $A \to C$ has cost $10$

So the shortest path from $A$ to $C$ is $A \to B \to C$.

3. Connectivity and Reachability

Reachability

• : A path shows whether one vertex can reach another. If there is at least one path between two vertices, they are said to be connected.

Connected graph

• : In an undirected graph, a graph is connected if every pair of vertices has a path between them.

Strong connectivity in directed graphs

• : In a directed graph, every vertex must be reachable from every other vertex through directed paths for the graph to be strongly connected.

Example:

If there is a path from $P$ to $Q$, then $Q$ is reachable from $P$. If no path exists, they are disconnected in that direction.

A small visual example:

A --- B --- C
      |
      D

Possible paths:

• $A \to B \to C$
• $A \to B \to D$

---

Working / Process

1. Start with a chosen vertex

• Select the beginning vertex of the path. In many problems, this is called the source vertex.
• Decide whether the graph is directed or undirected, because the allowed moves depend on this.

2. Move only along valid edges

• From the current vertex, go to an adjacent vertex connected by an edge.
• In directed graphs, follow the arrow direction only.
• Continue building the sequence while ensuring the path satisfies the required condition, such as being simple or shortest.

3. Check path properties

• Count the number of edges to determine the length.
• Verify whether vertices or edges are repeated.
• If weights are present, add them to find total cost.
• Compare different possible paths to identify the shortest or most efficient one.

Example process:

For graph edges:

• $A-B$
• $B-C$
• $C-D$
• $A-D$

Possible path from $A$ to $D$:

• $A \to D$ has length 1
• $A \to B \to C \to D$ has length 3

So the direct path is shorter in terms of edge count.

---

Advantages / Applications

Network routing

• : Paths are used to find how data travels through computer networks, making communication efficient and reliable.

Transportation systems

• : Road maps, railway systems, and airline routes use paths to calculate shortest routes, travel time, and cost.

Problem solving in algorithms

• : Path-related concepts are essential in graph algorithms such as breadth-first search, depth-first search, Dijkstra’s algorithm, and Bellman-Ford algorithm.

---

Summary

• A path is a sequence of connected vertices in a graph.
• Paths may be simple, closed, directed, undirected, or weighted.
• Path length and cost help determine route efficiency and shortest routes.
• Paths are central to connectivity, reachability, and many graph algorithms.