距离 (图论) 在图论中一张无向图里两顶点之间的距离是指他们之间最短路径英語shortest path的长度两顶点之间的距离也被称为测地距离英語geodesic distance需要注意的是两个顶点之间可能有多条最短路径如果两个顶点之间不存在路径即他们属于不同的连通分量那么按照传统它们距离被定义为无穷大 在有向图中如果从顶点 u displaystyle u 到顶点 v displaystyle v 存在有向路径英語directed path那么距离 d  u  v  displaystyle duv 被定义为从顶点  u displaystyle u 到顶点 v displaystyle v  之间最短有向路径的长度不同于无向图在有向图中 d  u  v  displaystyle duv 不一定和 d  v  u  displaystyle dvu 相等甚至有可能出现从顶点 u displaystyle u 到顶点 v displaystyle v 存在有向路径而从顶点 v displaystyle v 到顶点 u displaystyle u 却不存在有向路径的情况