Editing Shortest path problem (section)

==Definition==
The shortest path problem can be defined for [[Graph (discrete mathematics)|graphs]] whether [[Graph (discrete mathematics)#Undirected graph|undirected]], [[Graph (discrete mathematics)#Directed graph|directed]], or [[Mixed graph|mixed]]. The definition for undirected graphs states that every edge can be traversed in either direction. Directed graphs require that consecutive vertices be connected by an appropriate directed edge.<ref>{{cite book |last1=Deo |first1=Narsingh |title=Graph Theory with Applications to Engineering and Computer Science |date=17 August 2016 |publisher=Courier Dover Publications |isbn=978-0-486-80793-5 |url=https://books.google.com/books?id=uk1KDAAAQBAJ |language=en}}</ref>

Two vertices are adjacent when they are both incident to a common edge. A [[Path (graph theory)|path]] in an undirected graph is a [[sequence]] of vertices <math>P = ( v_1, v_2, \ldots, v_n ) \in V \times V \times \cdots \times V</math> such that <math>v_i</math> is adjacent to <math>v_{i+1}</math> for <math>1 \leq i < n</math>. Such a path <math>P</math> is called a path of length <math>n-1</math> from <math>v_1</math> to <math>v_n</math>. (The <math>v_i</math> are variables; their numbering relates to their position in the sequence and need not relate to a canonical labeling.)

Let <math>E = \{e_{i, j}\}</math> where <math>e_{i, j}</math> is the edge incident to both <math>v_i</math> and <math>v_j</math>. Given a [[Function (mathematics)#Real function|real-valued]] weight function <math>f: E \rightarrow \mathbb{R}</math>, and an undirected (simple) graph <math>G</math>, the shortest path from <math>v</math> to <math>v'</math> is the path <math>P = ( v_1, v_2, \ldots, v_n )</math> (where <math>v_1 = v</math> and <math>v_n = v'</math>) that over all possible <math>n</math> minimizes the sum <math>\sum_{i =1}^{n-1} f(e_{i, i+1}).</math> When each edge in the graph has unit weight or <math>f: E \rightarrow \{1\}</math>, this is equivalent to finding the path with fewest edges.

The problem is also sometimes called the '''single-pair shortest path problem''', to distinguish it from the following variations:
* The '''single-source shortest path problem''', in which we have to find shortest paths from a source vertex ''v'' to all other vertices in the graph.
* The '''single-destination shortest path problem''', in which we have to find shortest paths from all vertices in the directed graph to a single destination vertex ''v''. This can be reduced to the single-source shortest path problem by reversing the arcs in the directed graph.
* The '''all-pairs 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 single-pair shortest path algorithm on all relevant pairs of vertices.