The distance d(u, v) between two vertices u and v of a finite graph is the minimum length of the paths connecting them (i.e., the length of a graph geodesic). If no such path exists (i.e., if the vertices lie in different connected components), then the distance is set equal to ∞. In a grid graph the distance between two vertices is the sum of the "vertical" and the "horizontal" distances (right figure above). The matrix (d_(i j)) consisting of all distances from vertex v_i to vertex v_j is known as the all-pairs shortest path matrix, or more simply, the graph distance matrix.

all-pairs shortest path | Bellman-Ford algorithm | Dijkstra's algorithm | distance graph | Floyd-Warshall algorithm | girth | graph circumference | graph diameter | graph distance matrix | graph geodesic | shortest path problem