Distance (graph theory)

iIn the mathematical field of graph theory, the distance between two vertices in a graph is the number of edges in a shortest path (also called a graph geodesic) connecting them. This is also known as the geodesic distance or shortest-path distance.^[1] Notice that there may be more than one shortest path between two vertices.^[2] If there is no path connecting the two vertices, i.e., if they belong to different connected components, then conventionally the distance is defined as infinite.

In the case of a directed graph the distance d(u,v) between two vertices u and v is defined as the length of a shortest directed path from u to v consisting of arcs, provided at least one such path exists.^[3] Notice that, in contrast with the case of undirected graphs, d(u,v) does not necessarily coincide with d(v,u)—so it is just a quasi-metric, and it might be the case that one is defined while the other is not.

In graph theory, distances between nodes can be represented computationally by using a distance matrix (also called the all-pairs shortest-path matrix). This is the square matrix ${\displaystyle (D=(d_{ij}))}$, where each entry ${\displaystyle (d_{ij})}$ indicates the length of a shortest path between the two vertices ${\displaystyle (v_{i})}$ and ${\displaystyle (v_{j})}$.^[4]

Distance matrices have several applications, which include telecommunications and chemistry. In chemical graph theory, multiple topological indices that characterize molecular structure were able to be derived from the distance matrix.^[5]

Beyond exact matrix representations, graph distances can also be represented using metric embeddings. This approach maps the vertices of a graph to points in a geometric space (such as Euclidean space) in a way that preserves the graph distances as closely as possible.^[6]

In a directed graph, edges have an assigned direction, meaning travel between vertices is not necessarily bidirectional. As a result, the distance from ${\textstyle u}$ to ${\displaystyle v}$ may differ from the distance from ${\displaystyle v}$ to ${\displaystyle u}$. This makes directed graph distance a quasi-metric rather than a true metric.

Formally, for vertices ${\displaystyle u}$ and ${\displaystyle v}$ in a directed graph ${\displaystyle G}$, it is not guaranteed that ${\displaystyle d(u,v)=d(v,u)}$, and ${\displaystyle d(u,v)}$ may be undefined if no directed path from ${\displaystyle u}$ to ${\displaystyle v}$ exists.^[7]

A metric space defined over a set of points in terms of distances in a graph defined over the set is called a graph metric. The vertex set (of an undirected graph) and the distance function form a metric space, if and only if the graph is connected.

The eccentricity ϵ(v) of a vertex v is the greatest distance between v and any other vertex; in symbols,

${\displaystyle \epsilon (v)=\max _{u\in V}d(v,u).}$

It can be thought of as how far a node is from the node most distant from it in the graph.

The radius r of a graph is the minimum eccentricity of any vertex or, in symbols,

${\displaystyle r=\min _{v\in V}\epsilon (v)=\min _{v\in V}\max _{u\in V}d(v,u).}$

The diameter d of a graph is the maximum eccentricity of any vertex in the graph. That is, d is the greatest distance between any pair of vertices or, alternatively,

${\displaystyle d=\max _{v\in V}\epsilon (v)=\max _{v\in V}\max _{u\in V}d(v,u).}$

To find the diameter of a graph, first find the shortest path between each pair of vertices. The greatest length of any of these paths is the diameter of the graph.

A central vertex in a graph of radius r is one whose eccentricity is r—that is, a vertex whose distance from its furthest vertex is equal to the radius, equivalently, a vertex v such that ϵ(v) = r.

A peripheral vertex in a graph of diameter d is one whose eccentricity is d—that is, a vertex whose distance from its furthest vertex is equal to the diameter. Formally, v is peripheral if ϵ(v) = d.

A pseudo-peripheral vertex v has the property that, for any vertex u, if u is as far away from v as possible, then v is as far away from u as possible. Formally, a vertex v is pseudo-peripheral if, for each vertex u with d(u,v) = ϵ(v), it holds that ϵ(u) = ϵ(v).

A level structure of the graph, given a starting vertex, is a partition of the graph's vertices into subsets by their distances from the starting vertex.

A geodetic graph is one for which every pair of vertices has a unique shortest path connecting them. For example, all trees are geodetic.^[8]

The weighted shortest-path distance generalises the geodesic distance to weighted graphs. In this case it is assumed that the weight of an edge represents its length or, for complex networks the cost of the interaction, and the weighted shortest-path distance d^W(u, v) is the minimum sum of weights across all the paths connecting u and v. See the shortest path problem for more details and algorithms.

Many sparse matrix and graph algorithms require a starting vertex of high eccentricity, defined as $${\displaystyle \epsilon (v)=\max _{u\in V}d(v,u).}$$ A peripheral vertex, whose eccentricity equals the graph's diameter, would be ideal but is typically expensive to locate since it requires all-pairs distance information. A pseudo-peripheral vertex is a vertex whose eccentricity is close to the diameter; it can be found cheaply and serves as an effective substitute in practice.

The standard heuristic is the George–Liu algorithm:^[9]

1. Choose any vertex ${\displaystyle u\in V}$.
2. Among all vertices at maximum distance from ${\displaystyle u}$, let ${\displaystyle v}$ be one of minimum degree.
3. If ${\displaystyle \epsilon (v)>\epsilon (u)}$, set ${\displaystyle u:=v}$ and return to step 2; otherwise ${\displaystyle u}$ is a pseudo-peripheral vertex.

The same procedure in pseudocode, using breadth-first search (BFS) to compute eccentricities:

function PseudoPeripheral(G = (V, E)):
    choose any u ∈ V
    loop
        BFS from u to obtain ε(u) and F = {w : d(u, w) = ε(u)}
        let v ← vertex in F of minimum degree
        if ε(v) > ε(u) then u ← v
        else return u

Pseudo-peripheral vertices are most commonly used as starting points for bandwidth and profile reduction orderings of sparse matrices, particularly the reverse Cuthill–McKee method. Comparative evaluations of seven pseudoperipheral vertex finders have found that the George–Liu algorithm remains competitive with more recent alternatives on matrices with symmetric sparsity patterns.^[10]

A tree is a connected, acyclic graph in which there is exactly one simple path between any pair of vertices. This makes the distance d(u, v) uniquely determined, unlike in general graphs where multiple shortest paths may exist.^[11]

For a rooted tree, the distance between two vertices can be computed using their lowest common ancestor (LCA):

${\displaystyle d(u,v)=\operatorname {depth} (u)+\operatorname {depth} (v)-2\cdot \operatorname {depth} (\operatorname {LCA} (u,v))}$

where depth(v) is the number of edges from the root to v.

The diameter of a tree always occurs between two leaf nodes and can be found in O(n) time using two breadth-first searches. The center — the vertex minimizing eccentricity — is found by iteratively pruning leaf nodes until one or two vertices remain.^[12]

Graph distance has practical applications across several domains of computer science and engineering, where the theoretical notion of shortest-path distance translates directly into real-world problem solving.

Navigation and GPS systems

Road networks can be modeled as weighted graphs, where intersections represent vertices and roads represent edges with weights corresponding to distance or travel time. Finding the shortest route between two locations - as performed by GPS applications such as Google Maps is a direct application of weighted graph distance, typically computed using Dijkstra's algorithm.^[13]

Network routing protocols

In computer networking, protocols such as OSPF (Open Shortest Path First) model the internet as a weighted graph and use shortest-path distance to determine optimal routes for data packets between routers.^[13]

Social network analysis

Graph distance is used to quantify the degrees of separation between individuals in a social network. The average shortest-path distance across all pairs of nodes reflects how tightly connected a network is - a property central to the study of small-world networks.^[13]