Difference between revisions of "Shortest path"
From PEGWiki
(Created page with "The '''shortest paths''' problem is one of the most fundamental problems in graph theory. Given a directed graph <math>G = (V,E)</math>, possibly weighted, and a set of pairs...") |
(No difference)
|
Revision as of 19:57, 15 November 2010
The shortest paths problem is one of the most fundamental problems in graph theory. Given a directed graph 
, possibly weighted, and a set of pairs of vertices 
, the problem is to compute, for each 
, a path in 
from 
to 
(a list of vertices 
such that for all 
, 
) such that no other path in from to has a lower total weight.
Shortest paths in undirected graphs can be computed by replacing each undirected edge with two arcs of the same weight, one going in each direction, to obtain a directed graph.
Contents
Variations
Three variations of the shortest path algorithm exist, and they are discussed in the following sections.
- In the single-pair shortest path problem, there is only one pair
in the problem set. In other words the shortest path is desired between a single pair of vertices. - In the single-source shortest paths problem, the problem set is of the form
. One vertex, 
, is designated the source, and we wish to find the shortest paths from the source to all other vertices. (To solve the analogous single-destination shortest paths problem, we merely reverse the directions of all edges, which reduces it to single-source.) - In the all-pairs shortest paths problem, the problem set is
; that is, we wish to know the shortest paths from every vertex to every other vertex.
