Editing Distance (graph theory) (section)

{{Short description|Length of shortest path between two nodes of a graph}}

[[File:Distance (graph).svg|thumb|350px|Distances in various graphs between selected vertices. Some have no defined distance (marked as infinite distance) because they are in different [[component (graph_theory)|connected components]], or if edges in a directed graph can't lead from the first to the second. The latter may occur even if the distance in the other direction between the same two vertices is defined.]]

In the [[mathematics|mathematical]] field of [[graph theory]], the '''distance''' between two [[vertex (graph theory)|vertices]] in a [[Graph (discrete mathematics)|graph]] is the number of edges in a [[shortest path problem|shortest path]] (also called a '''graph geodesic''') connecting them.  This is also known as the '''geodesic distance''' or '''shortest-path distance'''.<ref>{{cite journal 
 |last = Bouttier  
 |first = Jérémie 
 |author2 = Di Francesco, P. 
 |author3 = Guitter, E. 
 |date = July 2003
 |title = Geodesic distance in planar graphs 
 |journal =  Nuclear Physics B
 |volume = 663 
 |issue = 3
 |pages = 535–567
 |quote = By distance we mean here geodesic distance along the graph, namely the length of any shortest path between say two given faces
 |doi = 10.1016/S0550-3213(03)00355-9
 |arxiv = cond-mat/0303272 
|bibcode = 2003NuPhB.663..535B 
 |s2cid = 119594729 
 }}</ref> Notice that there may be more than one shortest path between two vertices.<ref>{{cite web |url=http://mathworld.wolfram.com/GraphGeodesic.html |title=Graph Geodesic |access-date=2008-04-23 |last=Weisstein |first=Eric W. |author-link=Eric W. Weisstein |work=MathWorld--A Wolfram Web Resource |publisher=Wolfram Research |quote=The length of the graph geodesic between these points d(u,v) is called the graph distance between u and v |archive-date=2008-04-23 |archive-url=https://web.archive.org/web/20080423071114/http://mathworld.wolfram.com/GraphGeodesic.html |url-status=live }}</ref> If there is no [[Path (graph theory)|path]] connecting the two vertices, i.e., if they belong to different [[component (graph theory)|connected component]]s, then conventionally the distance is defined as infinite.

In the case of a [[directed graph]] the distance {{math|''d''(''u'',''v'')}} between two vertices {{mvar|u}} and {{mvar|v}} is defined as the length of a shortest directed path from {{mvar|u}} to {{mvar|v}} consisting of arcs, provided at least one such path exists.<ref>F. Harary, Graph Theory, Addison-Wesley, 1969, p.199.</ref> Notice that, in contrast with the case of undirected graphs, {{math|''d''(''u'',''v'')}} does not necessarily coincide with {{math|''d''(''v'',''u'')}}—so it is just a [[Metric (mathematics)#Quasimetrics|quasi-metric]], and it might be the case that one is defined while the other is not.