In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.

The problem of finding the shortest path between two intersections on a road map may be modeled as a special case of the shortest path problem in graphs, where the vertices correspond to intersections and the edges correspond to road segments, each weighted by the length or distance of each segment.

The shortest path problem can be defined for graphs whether undirected, directed, or mixed. The definition for undirected graphs states that every edge can be traversed in either direction. Directed graphs require that consecutive vertices be connected by an appropriate directed edge.

Two vertices are adjacent when they are both incident to a common edge. A path in an undirected graph is a sequence of vertices ${\displaystyle P=(v_{1},v_{2},\ldots ,v_{n})\in V\times V\times \cdots \times V}$ such that ${\displaystyle v_{i}}$ is adjacent to ${\displaystyle v_{i+1}}$ for ${\displaystyle 1\leq i<n}$. Such a path ${\displaystyle P}$ is called a path of length ${\displaystyle n-1}$ from ${\displaystyle v_{1}}$ to ${\displaystyle v_{n}}$. (The ${\displaystyle v_{i}}$ are variables; their numbering relates to their position in the sequence and need not relate to a canonical labeling.)

Let ${\displaystyle E=\{e_{i,j}\}}$ where ${\displaystyle e_{i,j}}$ is the edge incident to both ${\displaystyle v_{i}}$ and ${\displaystyle v_{j}}$. Given a real-valued weight function ${\displaystyle f:E\rightarrow \mathbb {R} }$, and an undirected (simple) graph ${\displaystyle G}$, the shortest path from ${\displaystyle v}$ to ${\displaystyle v'}$ is the path ${\displaystyle P=(v_{1},v_{2},\ldots ,v_{n})}$ (where ${\displaystyle v_{1}=v}$ and ${\displaystyle v_{n}=v'}$) that over all possible ${\displaystyle n}$ minimizes the sum ${\displaystyle \sum _{i=1}^{n-1}f(e_{i,i+1}).}$ When each edge in the graph has unit weight or ${\displaystyle f:E\rightarrow \{1\}}$, this is equivalent to finding the path with fewest edges.

The problem is also sometimes called the single-pair shortest path problem, to distinguish it from the following variations:

These generalizations have significantly more efficient algorithms than the simplistic approach of running a single-pair shortest path algorithm on all relevant pairs of vertices.

Several well-known algorithms exist for solving this problem and its variants.