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.
- 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.
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