Shortest Path Problem

The shortest path problem is a problem in graph theory and mathematical optimization: find a route between specified vertices whose edge weights have the smallest possible sum. Weights may represent distance, travel time, cost, or another additive quantity; “shortest” therefore need not mean geographically shortest. In an unweighted graph, the objective is to minimize the number of edges traversed. The problem is fundamental to network analysis and the design of efficient algorithms. (algs4.cs.princeton.edu)

Mathematical formulation

Let $G=(V,E)$ be a finite graph with vertex set $V$, edge set $E$, and a weight function $w:E\rightarrow\mathbb{R}$. In a directed graph, each edge must be traversed in its specified direction. For a route $P=(v_0,v_1,\ldots,v_k)$, its weight is

Given source $s$ and destination $t$, the shortest-path distance $\delta(s,t)$ is the minimum route weight when a finite minimum exists. An unreachable destination conventionally has distance $+\infty$. Several distinct routes can attain the same minimum. (ocw.mit.edu)

Terminology requires care: a simple path repeats no vertices, whereas a walk may repeat them. Standard shortest-path formulations allow walks but, when no relevant negative cycle exists, a minimum-weight walk can be chosen to be a simple path. A negative-weight cycle has a negative sum of edge weights. If such a cycle is reachable from $s$ and can reach $t$, repeated traversal makes the route cost arbitrarily small; its infimum is $-\infty$, rather than a finite shortest distance. A negative cycle elsewhere need not affect the particular pair. (ocw.mit.edu)

Principal variants

The single-pair problem concerns one source and one destination. The single-source problem finds distances from one source to every vertex, while the all-pairs problem finds distances for every ordered pair. A single-destination problem can be converted into a single-source problem by reversing all directed edges. (ocw.mit.edu)

Output may consist only of distances or may include predecessor information for reconstructing routes. When finite shortest paths exist from a source to its reachable vertices, suitable predecessor choices form a shortest-path tree. This compact representation avoids storing every route separately. (algs4.cs.princeton.edu)

Optimal substructure and relaxation

Shortest paths exhibit optimal substructure: every contiguous subpath of a shortest path is itself shortest between its endpoints. Otherwise, replacing that segment with a cheaper route would reduce the total weight. This property underlies both dynamic programming formulations and correctness proofs. (ocw.mit.edu)

Many algorithms maintain tentative distances $d[v]$, initially setting $d[s]=0$ and all other values to $+\infty$. The operation called edge relaxation examines an edge $(u,v)$ and updates

If this improves the estimate, the predecessor of $v$ is also updated. Algorithms differ principally in the order and frequency of these operations. (ocw.mit.edu)

Single-source algorithms

Algorithm choice depends on edge weights and graph structure. With $n=|V|$ and $m=|E|$, standard running-time bounds, expressed using big-O notation, include:

These bounds describe standard implementations rather than every possible optimization. (algs4.cs.princeton.edu)

Breadth-first search explores vertices in increasing numbers of edges from the source. Acyclic graphs admit topological sorting, allowing each vertex’s outgoing edges to be relaxed after its predecessors have been processed, even when weights are negative. (algs4.cs.princeton.edu)

Dijkstra’s algorithm repeatedly selects the smallest tentative distance through a priority queue. Nonnegative weights justify finalizing that distance; ordinary implementations that permanently finalize vertices are not generally correct with negative edges. Bellman–Ford instead makes repeated passes over all edges. After $n-1$ passes, finite shortest distances are established when no reachable negative cycle exists; a further improvement reveals a reachable negative cycle. (ocw.mit.edu)

All-pairs and heuristic search

The Floyd–Warshall algorithm computes all-pairs distances by progressively allowing more vertices as intermediates. It uses the recurrence

with $O(n^3)$ time and $O(n^2)$ space. Johnson’s algorithm offers another approach, especially for sparse graphs: Bellman–Ford supplies vertex potentials that reweight edges to nonnegative values without changing shortest-route choices, after which Dijkstra runs from each source. (ocw.mit.edu)

For a specified destination, A* search orders exploration by $f(v)=g(v)+h(v)$, combining the known cost from the source with a heuristic estimate of remaining cost. An admissible heuristic never overestimates the true remaining distance. A consistent heuristic additionally satisfies $h(u)\leq w(u,v)+h(v)$, with zero at the goal; this supports optimal graph search without reopening finalized vertices. Setting $h=0$ gives uniform-cost search. (cs.cmu.edu)

Applications and implementation

Shortest-path models support transportation routing, network communication, and state-space search. The Open Shortest Path First routing protocol uses Dijkstra’s algorithm. Correct modeling requires weights to represent the intended additive objective: minimizing distance and minimizing travel time can produce different routes. (algs4.cs.princeton.edu)

Implementations must distinguish unreachable vertices from very large finite distances and reconstruct routes consistently when ties occur. Floating-point arithmetic introduces rounding effects, while bounded integer arithmetic can overflow during distance addition. Mathematical correctness assumes these operations preserve the comparisons on which relaxation depends. (algs4.cs.princeton.edu)

References

1. Shortest Pathsalgs4.cs.princeton.edu
2. Lecture 15: Shortest Paths I: Introocw.mit.edu
3. Lecture 15: Shortest Paths I: Introocw.mit.edu
4. Lecture 16: Shortest Paths II: Dijkstraocw.mit.edu
5. Algorithms and Data Structures Cheatsheetalgs4.cs.princeton.edu
6. BreadthFirstPaths (Algorithms 4/e)algs4.cs.princeton.edu
7. BellmanFordSP (Algorithms 4/e)algs4.cs.princeton.edu
8. Lecture 19: All-pairs Shortest Pathsocw.mit.edu
9. Search and Gamescs.cmu.edu