HOME
        TheInfoList






In 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.[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 between two vertices and is defined as the length of a shortest directed path from to consisting of arcs, provided at least one such path exists.[3] Notice that, in contrast with the case of undirected graphs, does not necessarily coincide with , and it might be the case that one is defined while the other is not.