GraphDistanceMatrix

GraphDistanceMatrix[g]

给出图 g 的顶点之间的距离组成的矩阵.

GraphDistanceMatrix[g,d]

给出图 g 中最大距离为 d 的顶点之间的距离组成的矩阵.

GraphDistanceMatrix[{vw,…},…]

使用规则 vw 指定图 g.

更多信息和选项

  • GraphDistanceMatrix 也被称为最短路径矩阵.
  • GraphDistanceMatrix 返回一个 SparseArray 对象或者一个普通矩阵.
  • 距离矩阵 dij 的元素给出从顶点 vi 到顶点 vj 的最短距离.
  • 距离矩阵的对角线元素 dii 总是0.
  • 元素 dij 是 Infinity (∞) ，如果从顶点 vi 到顶点 vj 不存在路径.
  • 在 GraphDistanceMatrix[g,d] 中，一个元素 dij 为 Infinity，如果在 d 步或者更少的步数内，不存在从顶点 vi 到顶点 vj 的路径.
  • 假设顶点 vi 以 VertexList[g] 的顺序给出.
  • 对于加权图，该距离指的是从顶点 vi 到顶点 vj 沿任何路径的权值之和的最小值.
  • 可以给出下列选项：
  • EdgeWeightAutomatic各边权值
    Method Automatic使用的方法
  • 可能的 Method 设置包括 "Dijkstra"、"FloydWarshall" 和 "Johnson".

范例

打开所有单元关闭所有单元

基本范例  (1)

给出 Petersen 图的距离矩阵：

范围  (8)

GraphDistanceMatrix 适用于无向图：

也适用于有向图：

加权图：

多图：

混合图：

使用规则指定图：

对于规模适度的图，提取矩阵的单个列：

使用 GraphDistance 来计算相同的结果花费更多时间：

GraphDistanceMatrix 适用于大规模图：

当只需要一个列，并且图是大规模的，使用 GraphDistance 通常更快：

选项  (6)

Method  (6)

取决于输入，自动选择方法：

"UnitWeight" 方法对每条边使用1作为权值：

"Dijkstra" 可用于权值只为正值的边构成的图：

"FloydWarshall" 可用于边权值含有负数的有向图：

"Johnson" 可用于边权值包含负数的有向图：

"Johnson" 对于稀疏图比 "FloydWarshall" 方法更快：

应用  (2)

考虑整个图去，求顶点的离心率：

对于强连通图，结果与 VertexEccentricity 一致：

求一个连通图中每个顶点的顶点离心率：

检测结果：

属性和关系  (5)

距离矩阵的行和列遵循由 VertexList 给出的顺序：

距离矩阵的对角线元素总是零：

距离矩阵可以通过使用 GraphDistance 求得：

在一个连通图中，VertexEccentricity 可以从距离矩阵得到：

属于不同连通分量的两个顶点之间的距离是 Infinity：

可能存在的问题  (2)

矩阵的索引可能与我们所期望的不同，它们并没有与顶点之间的关联：

从 2 到 3 的距离不位于预期的矩阵位置上：

原因是顶点没有以预期顺序排列：

通过当调用诸如 Graph 的函数时明确列出顶点，求解该问题：

现在在预期的位置上可以找到距离：

"BellmanFord" 不是一个有效的 Method 选项：

而是使用 "FloydWarshall"、"Johnson" 或者 Method 的默认选项：

巧妙范例  (1)

Wolfram Research (2010)，GraphDistanceMatrix，Wolfram 语言函数，https://reference.wolfram.com/language/ref/GraphDistanceMatrix.html （更新于 2015 年）.

文本

Wolfram Research (2010)，GraphDistanceMatrix，Wolfram 语言函数，https://reference.wolfram.com/language/ref/GraphDistanceMatrix.html （更新于 2015 年）.

CMS

Wolfram 语言. 2010. "GraphDistanceMatrix." Wolfram 语言与系统参考资料中心. Wolfram Research. 最新版本 2015. https://reference.wolfram.com/language/ref/GraphDistanceMatrix.html.

APA

Wolfram 语言. (2010). GraphDistanceMatrix. Wolfram 语言与系统参考资料中心. 追溯自 https://reference.wolfram.com/language/ref/GraphDistanceMatrix.html 年

BibTeX

@misc{reference.wolfram_2024_graphdistancematrix, author="Wolfram Research", title="{GraphDistanceMatrix}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/GraphDistanceMatrix.html}", note=[Accessed: 22-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_graphdistancematrix, organization={Wolfram Research}, title={GraphDistanceMatrix}, year={2015}, url={https://reference.wolfram.com/language/ref/GraphDistanceMatrix.html}, note=[Accessed: 22-November-2024 ]}