Distance (graph theory)

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.

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.

A geodetic graph is one for which every pair of vertices has a unique shortest path connecting them.

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 dW(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.

Often peripheral sparse matrix algorithms need a starting vertex with a high eccentricity.

Distances in various graphs between selected vertices. Some have no defined distance (marked as infinite distance) because they are in different 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.