<< Chapter < Page | Chapter >> Page > |
(From Wikipedia, the free encyclopedia)
In graph theory, the shortest path problem is the problem of finding a path between two vertices such that the sum of the weights of its constituent edges is minimized. An example is finding the quickest way to get from one location to another on a road map; in this case, the vertices represent locations and the edges represent segments of road and are weighted by the time needed to travel that segment.
Formally, given a weighted graph (that is, a set V of vertices, a set E of edges, and a real-valued weight function f : E → R), and one element v of V, find a path P from v to each v' of V so that
is minimal among all paths connecting v to v' .
Sometimes it is called the single-pair shortest path problem, to distinguish it from the following generalizations:
Both these generalizations have significantly more performant algorithms in practice than simply running a single-pair shortest path algorithm on all relevant pairs of vertices.
The most important algorithms for solving this problem are:
Shortest path algorithms are applied in an obvious way to automatically find directions between physical locations, such as driving directions on web mapping websites like Mapquest.
If one represents a nondeterministic abstract machine as a graph where vertices describe states and edges describe possible transitions, shortest path algorithms can be used to find an optimal sequence of choices to reach a certain goal state, or to establish lower bounds on the time needed to reach a given state. For example, if vertices represents the states of a puzzle like a Rubik's Cube and each directed edge corresponds to a single move or turn, shortest path algorithms can be used to find a solution that uses the minimum possible number of moves.
In a networking or telecommunications mindset, this shortest path problem is sometimes called the min-delay path problem and usually tied with a widest path problem. e.g.: Shortest (min-delay) widest path or Widest shortest (min-delay) path.
Notification Switch
Would you like to follow the 'Data structures and algorithms' conversation and receive update notifications?