Path (Graph Theory)
A path in a graph is a sequence of vertices connected by edges where no vertex is repeated, representing a route through the graph.
Definition
A path in a graph is a route from one vertex to another that follows edges without revisiting any vertex, a trail with no backtracking to a place you have already been. Formally, a path is a sequence of distinct vertices $v_0, v_1, \ldots, v_k$ such that each consecutive pair $\{v_i, v_{i+1}\}$ is an edge; the length of the path is $k$, a closed path ($v_0 = v_k$) is a cycle, and a graph is connected if a path exists between every pair of vertices. The distance $d(u,v)$ is the length of the shortest path from $u$ to $v$; the diameter of $G$ is $\max_{u,v} d(u,v)$ and the girth is the length of the shortest cycle, with shortest paths found by Dijkstra's (non-negative weights) or Bellman-Ford (negative weights allowed, detects negative cycles).
Example
In a city map graph, a path from Home to School might go Home, Library, Park, School, visiting each place exactly once. In a graph with vertices $\{1,2,3,4\}$ and edges $\{12,23,34,14\}$, the path $1$-$2$-$3$-$4$ has length $3$ and is Hamiltonian (visits every vertex exactly once). The P vs. NP problem connects closely here: finding a Hamiltonian path is NP-complete, while finding an Eulerian path (traversing all edges once) is solvable in polynomial time, and finding shortest path is in P, a dichotomy showing how slight changes in constraints dramatically alter algorithmic difficulty.
Key Insight
Finding the shortest path between two vertices is one of the most important problems in graph theory, solved by algorithms like Dijkstra's and Bellman-Ford. In algebraic graph theory, the number of walks of length $k$ from $u$ to $v$ equals the $(u,v)$ entry of $A^k$ (the $k$th power of the adjacency matrix), connecting path counting to linear algebra.