Shortest path problem
Problem of minimizing total edge weight between two graph vertices.
The shortest path problem is a fundamental problem in graph theory, concerned with finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized. It can be modeled for real-world scenarios, such as finding the shortest route between two intersections on a road map, where vertices represent intersections and edges represent road segments weighted by distance. The problem can be defined for undirected, directed, or mixed graphs. In an undirected graph, every edge can be traversed in either direction, while directed graphs require consecutive vertices to be connected by an appropriately directed edge. A path is a sequence of vertices where each consecutive pair is adjacent, and its length is the number of edges. Given a real-valued weight function on edges, the shortest path from one vertex to another is the path that minimizes the sum of edge weights; when all edges have unit weight, this is equivalent to finding the path with the fewest edges.
The problem is often called the single-pair shortest path problem to distinguish it from variations: the single-source problem, which finds shortest paths from a source vertex to all others; the single-destination problem, which finds shortest paths from all vertices to a single destination (reducible to the single-source problem by reversing arcs); and the all-pairs problem, which finds shortest paths between every pair of vertices. These generalizations have significantly more efficient algorithms than running a single-pair algorithm on all relevant pairs. Notable algorithms include Dijkstra’s algorithm for single-source problems with non-negative weights, the Bellman–Ford algorithm for single-source problems with negative weights, the A* search algorithm for single-pair problems using heuristics, the Floyd–Warshall algorithm for all-pairs shortest paths, and Johnson’s algorithm for all-pairs problems, which can be faster on sparse graphs. The Viterbi algorithm solves the shortest stochastic path problem with an additional probabilistic weight on each node. For directed acyclic graphs, an algorithm using topological sorting can solve the single-source problem in linear time regardless of edge weights. Shortest path algorithms are also applied to network flow problems, where a residual graph is created and shortest paths are iteratively found and augmented to max
- field
- Graph theory, computer science, operations research
- known_for
- Finding the path between vertices with minimum total edge weight
- variants
- Single-pair, single-source, single-destination, all-pairs shortest path problems
- key_algorithms
- Dijkstra's algorithm, Bellman–Ford algorithm, A* search algorithm, Floyd–Warshall algorithm, Johnson's algorithm, Viterbi algorithm
Lore & Background
The shortest path problem can be defined for undirected, directed, or mixed graphs. In an undirected graph, every edge can be traversed in either direction, while directed graphs require consecutive vertices to be connected by an appropriate directed edge. A path is a sequence of vertices where each consecutive pair is adjacent, and its length is the number of edges minus one. The problem minimizes the sum of edge weights along the path, and when each edge has unit weight, it reduces to finding the path with the fewest edges. This core formulation is known as the single-pair shortest path problem, but several important variations exist. The single-source shortest path problem requires finding shortest paths from a source vertex to all other vertices. The single-destination problem, which can be solved by reversing the graph's arcs and applying a single-source algorithm, seeks shortest paths from all vertices to a single destination. The all-pairs shortest path problem computes shortest paths between every pair of vertices. These generalizations allow for significantly more efficient algorithms than repeatedly solving single-pair instances. Notable algorithms include Dijkstra's algorithm for non-negative weights, the Bellman–Ford algorithm for graphs that may contain negative edge weights, and the Floyd–Warshall and Johnson's algorithms for all-pairs problems. In directed acyclic graphs, topological sorting yields a solution in linear time. Shortest path problems also have applications in network flow, where they can be used to find augmenting paths in residual graphs to maximize flow from a source to a sink.
Reader's Guide
The shortest path problem is central to graph theory and has numerous practical applications, including network flow problems. It can be used to solve certain network flow problems by transforming them into a series of shortest path problems: creating a residual graph, finding the shortest path from source to sink, augmenting flow along that path, and updating the residual graph. Several algorithms exist for different variants: Dijkstra's algorithm for single-source with non-negative weights, Bellman–Ford for single-source with negative weights, A* for single-pair with heuristics, Floyd–Warshall and Johnson's for all-pairs, and Viterbi for stochastic paths with probabilistic node weights. The problem is also called the single-pair shortest path problem to distinguish it from generalizations like single-source, single-destination, and all-pairs, which have more efficient algorithms than running a single-pair algorithm on all relevant pairs.
Did You Know?
- The shortest path problem can be defined for undirected, directed, or mixed graphs.
- When each edge has unit weight, the problem is equivalent to finding the path with the fewest edges.
- The single-destination shortest path problem can be reduced to the single-source problem by reversing the arcs in the directed graph.
- An algorithm using topological sorting can solve the single-source shortest path problem in time Θ(E + V) in arbitrarily-weighted directed acyclic graphs.
Frequently Asked Questions
Who is Shortest path problem?
It is a central question in graph theory, computer science, and operations research that asks for the route between two chosen vertices whose total edge cost is as small as possible. Think of it as the canonical 'find the cheapest way across a network' challenge.
What are Shortest path problem's powers and role?
It appears in several distinct variants—single-pair, single-source, single-destination, and all-pairs—each imposing slightly different constraints on which routes you must compute. In the real world it models GPS routing, network packet forwarding, and supply-chain logistics.
How does Shortest path problem's story end?
The resolution depends on the graph's weight properties: Dijkstra's algorithm is the go-to for non-negative edges, Bellman–Ford handles negative weights, and Floyd–Warshall or Johnson's algorithm cover the all-pairs case. A* search adds a heuristic layer to prune the search space in large instances.
Why is Shortest path problem so important in the canon?
It is the backbone of countless practical applications, from planning the fastest driving route to optimizing data flow across a network. It also serves as a building block in complexity theory, since many harder optimization problems either reduce to it or are analyzed by comparing against it.
Who are Shortest path problem's key allies?
Its main supporting cast consists of Dijkstra's, Bellman–Ford, A*, Floyd–Warshall, Johnson's, and the Viterbi algorithm, each engineered for a different weight regime or graph structure. Together they form a complete toolkit that fans can match to whichever variant they are tackling.
More in Complexity Theory 1-24
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record