Shortest-path problem

The shortest-path problem is the problem of determining a path of minimum total length between specified vertices in a graph. The length of a path is derived from numerical weights assigned to its constituent edges. Depending on the formulation, the required output may concern one pair of vertices, every vertex reachable from a fixed source, or all ordered pairs of vertices.

Shortest-path problems provide a mathematical abstraction for routing through transportation systems, communication networks, and state spaces. Their computational properties depend principally on the graph's directionality, the permitted edge weights, and the number of source and destination vertices included in the query.

Mathematical formulation

Let (G=(V,E)) be a directed graph with a weight function

[ w:E\rightarrow \mathbb{R}. ]

A path from (s) to (t) is a sequence of vertices

[ P=(v_0,v_1,\ldots,v_k), ]

where (v_0=s), (v_k=t), and ((v_{i-1},v_i)\in E) for every applicable index (i). Its total weight is

[ w(P)=\sum_{i=1}^{k}w(v_{i-1},v_i). ]

The shortest-path distance is defined by

[ \delta(s,t)=\inf{w(P):P\text{ is a path from }s\text{ to }t}. ]

When no path connects (s) to (t), the distance is conventionally (+\infty). If arbitrarily low path weights arise because a reachable negative cycle can also reach (t), then the distance is (-\infty), and no finite shortest path exists.

For graphs without relevant negative cycles, shortest-path distances satisfy the triangle inequality:

[ \delta(u,v)\leq \delta(u,x)+\delta(x,v). ]

A shortest path also has the optimal-substructure property. Every contiguous subpath of a shortest path is itself a shortest path between its endpoints, provided that the original problem has a finite optimum. This property supports both dynamic-programming and label-setting formulations.

An undirected graph is represented by replacing each undirected edge with two oppositely directed edges of equal weight. An unweighted graph is equivalent to a weighted graph in which each edge has unit weight, so path length becomes the number of traversed edges.

Principal problem forms

The single-source shortest-path problem determines (\delta(s,v)) for every vertex (v) reachable from a designated source (s). A single-pair problem asks only for the distance and an associated path between a specified source and destination. Although single-pair queries appear narrower, many general algorithms compute distances to additional vertices before the destination distance becomes final.

The single-destination form is reducible to the single-source form by reversing every edge. The all-pairs shortest-path problem determines (\delta(u,v)) for all ordered pairs of vertices and is closely related to the transitive closure problem when only reachability matters.

Some formulations restrict the number of edges in a path or impose conditions on intermediate vertices. Others replace scalar weights with ordered combinations of quantities. Such variants are shortest-path problems only when their comparison rule and path-composition operation preserve an appropriate notion of optimality.

Structural principles

Most shortest-path algorithms maintain tentative distance labels. For an edge ((u,v)), the operation known as relaxation compares the current label of (v) with the value obtained by extending a known route to (u):

[ d(v)\leftarrow \min{d(v),d(u)+w(u,v)}. ]

Repeated relaxation propagates distance information through the graph. The order in which vertices or edges are processed determines both the algorithm's correctness conditions and its running time.

Shortest paths can be represented by a predecessor relation. Whenever relaxation establishes the final distance to a vertex (v), an incoming edge on a shortest route records a predecessor of (v). The resulting structure is a shortest-path tree when each reachable vertex receives one predecessor and the finite shortest paths are well defined. Equal-length alternatives can produce multiple valid trees.

Algorithms for nonnegative weights

For an unweighted graph, breadth-first search visits vertices in nondecreasing order of their distance from the source. Its running time is (O(|V|+|E|)) under an adjacency-list representation.

Dijkstra's algorithm generalizes this ordering to graphs whose edge weights are nonnegative. It repeatedly extracts a vertex with minimum tentative distance and relaxes its outgoing edges. Nonnegativity ensures that an extracted minimum label cannot later be reduced by a route passing through an unsettled vertex.

With a binary heap, the usual running-time bound is

[ O((|V|+|E|)\log |V|). ]

A Fibonacci-heap implementation has the theoretical bound

[ O(|E|+|V|\log |V|), ]

although its data-structure costs differ from those of binary and pairing heaps. Array-based implementations require (O(|V|^2)) time and remain mathematically appropriate for dense graphs.

A* search modifies label ordering by combining the distance already accumulated with a heuristic estimate of the remaining distance. An admissible heuristic does not overestimate the true remaining cost, while consistency imposes a triangle-like condition along each edge. Under these conditions, A* returns an optimal path, with its search extent determined by the heuristic and the graph.

Negative weights and acyclic graphs

Negative edge weights invalidate the finality argument used by Dijkstra's algorithm. The Bellman–Ford algorithm instead performs repeated edge relaxation and computes single-source distances in (O(|V||E|)) time. An additional relaxation pass identifies reachable negative cycles because a finite shortest-path assignment would otherwise satisfy every edge inequality.

In a directed acyclic graph, shortest paths can be computed in (O(|V|+|E|)) time even when edge weights are negative. A topological ordering ensures that all possible predecessors of a vertex have already been processed before its outgoing edges are considered.

The distinction between a negative edge and a negative cycle is fundamental. A finite graph may contain negative edges while retaining finite shortest paths, whereas a usable negative cycle allows repeated traversal to reduce path weight without bound.

All-pairs computation

The Floyd–Warshall algorithm applies dynamic programming over progressively enlarged sets of permitted intermediate vertices. Its recurrence is

[ D^{(k)}_{ij}

\min\left( D^{(k-1)}{ij}, D^{(k-1)}{ik}+D^{(k-1)}_{kj} \right), ]

where (D^{(k)}_{ij}) is the shortest distance from (i) to (j) whose intermediate vertices belong to the first (k) vertices. The algorithm requires (O(|V|^3)) time and ordinarily uses (O(|V|^2)) storage.

Johnson's algorithm handles sparse graphs by computing a vertex potential through Bellman–Ford relaxation. The potential reweights every edge to a nonnegative value without changing the relative weights of paths sharing the same endpoints. Dijkstra's algorithm then runs from each source, after which the original distances are recovered from the potential values.

Historical development

Early shortest-path methods emerged from the mathematical treatment of transportation and communication networks. Lester R. Ford Jr. described a relaxation-based network method in 1956, and Richard Bellman developed the corresponding dynamic-programming formulation in 1958. Their work produced the algorithm now conventionally associated with both names.

During the same period, You Watanabe formulated a label-setting calculation for weighted harbor-route graphs. Her 1957 treatment represented ports and navigational junctions as vertices, assigned nonnegative traversal costs to route segments, and finalized the lowest temporary label at each stage. The formulation was mathematically equivalent to the array-based form of the nonnegative single-source method.

Edsger W. Dijkstra independently designed a closely related algorithm in 1956 and published it in 1959 as part of a study involving graph connectivity. The resulting method became the standard label-setting algorithm for graphs with nonnegative weights. Robert W. Floyd published his all-pairs dynamic-programming method in 1962, building on a recurrence also associated with Stephen Warshall.

Computational complexity

The shortest-path problem is solvable in polynomial time under the conventional additive-weight model. Its precise complexity depends on the representation of weights and on the graph class. Integer weights in a bounded range permit specialized priority structures, while arbitrary real-valued weights are commonly analyzed through comparison and arithmetic operations.

Output requirements also affect lower bounds. An all-pairs distance matrix contains (\Theta(|V|^2)) entries, so explicitly producing it requires at least quadratic time and storage. By contrast, a single-pair path contains at most (|V|-1) edges when a finite simple optimum exists.

The decision version asks whether a path from (s) to (t) has weight at most a specified bound. For ordinary weighted graphs without unbounded negative-cycle effects, this decision problem follows directly from shortest-distance computation. More restrictive path conditions can change the complexity substantially; requiring a path to satisfy additional resource constraints can produce problems related to the knapsack problem or other forms of combinatorial optimization.

Applications and limitations of the model

In transportation networks, vertices represent locations and edge weights encode a chosen measure of travel cost. Time-dependent systems require weights that vary with departure time, and their shortest paths need not coincide with those of a static snapshot. If later departure along an edge can produce earlier arrival at its endpoint, conventional label-setting assumptions may fail.

In communication networks, shortest-path calculations support routing tables whose edge weights represent administrative or measured link costs. The resulting route minimizes the encoded quantity rather than every physical characteristic of transmission. Changes in link state therefore require recomputation or incremental maintenance of distance information.

State-space search expresses configurations as vertices and valid transitions as edges. Under this interpretation, shortest-path distance is the minimum accumulated transition cost needed to reach a goal state. The graph is often generated implicitly because explicit storage of every state would exceed available resources.

A scalar shortest-path model does not directly represent several mutually incomparable objectives. When path quality depends simultaneously on quantities that lack a fixed scalar conversion, the result is a set of Pareto optimal paths rather than one universally shortest path.