主题
Search

图的测地线

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本
GraphGeodesics

图的两个顶点 (u,v) 之间的最短路径，图 (Skiena 1990, p. 225)。可能有多条不同的最短路径，但长度都相同。图的测地线可以使用广度优先遍历 (Moore 1959) 或使用 Dijkstra 算法 (Skiena 1990, p. 225) 找到。图 g 从顶点 u 到顶点 v 的一条（可能是几条之一）图的测地线可以使用 Wolfram 语言 中的以下命令找到FindShortestPath[g, u, v]。这些点 d(u,v) 之间的图的测地线长度称为 u 和 v 之间的图距离。

给定图中最大测地线的长度称为图的直径，最小测地线的长度称为图的半径。

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

每对顶点之间都具有唯一测地线的图称为测地图。

另请参阅

所有点对最短路径, Bellman-Ford 算法, Dijkstra 算法, Floyd-Warshall 算法, 测地图, 图的直径, 图距离, 图距离矩阵, 最短路径问题

使用 探索

参考文献

Harary, F. 图论。 雷丁，马萨诸塞州：Addison-Wesley, p. 14, 1994.Moore, E. F. "迷宫中的最短路径。" In Proc. Internat. Symp. Switching Th., Part II. Cambridge, MA: Harvard University Press, pp. 285-292, 1959.Skiena, S. "最短路径。" §6.1 in 实现离散数学：组合数学和图论与 Mathematica。 雷丁，马萨诸塞州：Addison-Wesley, pp. 225-253, 1990.

在 上被引用

图的测地线

请引用为

Weisstein, Eric W. “图的测地线。” 来自 —— 资源。 https://mathworld.net.cn/GraphGeodesic.html

主题分类