Difference between revisions of "Shortest path"

From PEGWiki
Jump to: navigation, search
(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 G = (V,E), possibly weighted, and a set of pairs of vertices \{(u_1,v_1), ..., (u_n,v_n)\}, u_i, v_i \in V, the problem is to compute, for each i, a path in G from u_i to v_i (a list of vertices u_i = s_{i,0}, s_{i,1}, ..., s_{i,k} = v_i such that for all 0 \leq j < k, (s_{i,j},s_{i,j+1}) \in E) such that no other path in G from u_i to v_i 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.

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 (u,v) 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 \{u\} \times V. One vertex, u, 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 V \times V; that is, we wish to know the shortest paths from every vertex to every other vertex.

Single-source shortest paths

All-pairs shortest paths

Single-pair shortest path

References