距离 (图论)
圖上兩頂點的最短距離 / 维基百科,自由的 encyclopedia
在图论中,一张无向图里,两顶点之间的距离是指他们之间最短路径(英语:shortest path)[注 1]的长度,两顶点之间的距离也被称为测地距离(英语:geodesic distance)[1]。需要注意的是两个顶点之间可能有多条最短路径[2],如果两个顶点之间不存在路径(即他们属于不同的连通分量),那么按照传统它们距离被定义为无穷大。
在有向图中,如果从顶点 到顶点 存在有向路径(英语:directed path),那么距离 被定义为从顶点 到顶点 之间最短有向路径的长度[3]。不同于无向图,在有向图中 不一定和 相等[注 2],甚至有可能出现从顶点 到顶点 存在有向路径,而从顶点 到顶点 却不存在有向路径的情况。