Shortest path problem: Difference between revisions

Revision as of 13:54, 5 November 2024

Revision as of 05:19, 3 December 2024

Line 7:

==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]]. HereThe it is defineddefinition for undirected graphs; forstates directedthat graphsevery theedge definitioncan ofbe pathtraversed in either direction. Directed graphs requiresrequire 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.)

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 here relates to their position in the sequence and needs not to relate to any canonical labeling of the vertices.)

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.