图距离

距离 在有限图中两个顶点 和 之间是连接它们的路径的最小长度（即，图测地线 的长度）。如果不存在这样的路径（即，如果顶点位于不同的连通分量中），则距离被设置为 。在 网格图 中，两个顶点之间的距离是“垂直”和“水平”距离之和（上图右侧）。

矩阵 由从顶点 到顶点 的所有距离组成，被称为所有顶点对最短路径矩阵，或更简单地，图距离矩阵。