圖的測地線

圖的兩個頂點 之間的最短路徑，圖 (Skiena 1990, p. 225)。可能有多條不同的最短路徑，但長度都相同。圖的測地線可以使用廣度優先遍歷 (Moore 1959) 或使用 Dijkstra 演算法 (Skiena 1990, p. 225) 找到。圖 從頂點 到頂點 的一條（可能是幾條之一）圖的測地線可以使用 Wolfram 語言 中的以下命令找到FindShortestPath[g, u, v]。這些點 之間的圖的測地線長度稱為 和 之間的圖距離。

給定圖中最大測地線的長度稱為圖的直徑，最小測地線的長度稱為圖的半徑。

由從頂點 到頂點 的所有圖距離組成的矩陣 被稱為所有點對最短路徑矩陣，或更簡單地說，圖距離矩陣。

每對頂點之間都具有唯一測地線的圖稱為測地圖。