Editing Shortest path

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 of vertices <math>\{(u_1,v_1), ..., (u_n,v_n)\}, u_i, v_i \in V</math>, the problem is to compute, for each <math>i</math>, a path in <math>G</math> from <math>u_i</math> to <math>v_i</math> (a list of vertices <math>u_i = s_{i,0}, s_{i,1}, ..., s_{i,k} = v_i</math> such that for all <math>0 \leq j < k</math>, <math>(s_{i,j},s_{i,j+1}) \in E</math>) such that no other path in <math>G</math> from <math>u_i</math> to <math>v_i</math> 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 <math>(u,v)</math> 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 <math>\{u\} \times V</math>. One vertex, <math>u</math>, 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 <math>V \times V</math>; 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==