距离 (图论)
圖上兩頂點的最短距離 / 維基百科,自由的 encyclopedia
親愛的 Wikiwand AI, 讓我們通過簡單地回答這些關鍵問題來保持簡短:
你能列出最重要的事實和統計數據嗎 距离 (图论)?
為 10 歲的孩子總結這篇文章
顯示所有問題
在图论中,一张无向图里,两顶点之间的距离是指他们之间最短路径(英語:shortest path)[註 1]的长度,两顶点之间的距离也被称为测地距离(英語:geodesic distance)[1]。需要注意的是两个顶点之间可能有多条最短路径[2],如果两个顶点之间不存在路径(即他们属于不同的连通分量),那么按照传统它们距离被定义为无穷大。
在有向图中,如果从顶点 到顶点
存在有向路径(英語:directed path),那么距离
被定义为从顶点
到顶点
之间最短有向路径的长度[3]。不同于无向图,在有向图中
不一定和
相等[註 2],甚至有可能出现从顶点
到顶点
存在有向路径,而从顶点
到顶点
却不存在有向路径的情况。