
related topics 
{math, number, function} 
{line, north, south} 
{system, computer, user} 
{film, series, show} 
{specie, animal, plant} 

In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) 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 realvalued weight function f : E â†’ R), and one element v of V, find a path P from v to a v' of V so that
is minimal among all paths connecting v to v' .
The problem is also sometimes called the singlepair shortest path problem, to distinguish it from the following generalizations:
 The singlesource shortest path problem, in which we have to find shortest paths from a source vertex v to all other vertices in the graph.
 The singledestination shortest path problem, in which we have to find shortest paths from all vertices in the graph to a single destination vertex v. This can be reduced to the singlesource shortest path problem by reversing the edges in the graph.
 The allpairs shortest path problem, in which we have to find shortest paths between every pair of vertices v, v' in the graph.
These generalizations have significantly more efficient algorithms than the simplistic approach of running a singlepair shortest path algorithm on all relevant pairs of vertices.
Contents
Algorithms
The most important algorithms for solving this problem are:
Additional algorithms and associated evaluations may be found in Cherkassky et al.^{[1]}
Applications
Shortest path algorithms are applied to automatically find directions between physical locations, such as driving directions on web mapping websites like Mapquest or Google Maps. For this application fast specialized algorithms are available.^{[2]}
Full article ▸


related documents 
Calculus with polynomials 
Partial function 
Malleability (cryptography) 
Subtraction 
Hash collision 
Weierstrassâ€“Casorati theorem 
Byteorder mark 
Double negative elimination 
Algebraic extension 
BorelCantelli lemma 
Steiner system 
Residue (complex analysis) 
Extractor 
Subalgebra 
Nowhere dense set 
Category (mathematics) 
Magma computer algebra system 
Iteration 
Atlas Autocode 
Zeta distribution 
Dyadic rational 
Geometric mean 
Stirling number 
Static code analysis 
Degenerate distribution 
Cayley's theorem 
GNU Octave 
Bernoulli process 
Pseudometric space 
T1 space 
