GraphDistanceMatrix
GraphDistanceMatrix
给出图 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 沿任何路径的权值之和的最小值.
- 可以给出下列选项：
-
EdgeWeight Automatic 各边权值 Method Automatic 使用的方法 - 可能的 Method 设置包括 "Dijkstra"、"FloydWarshall" 和 "Johnson".
范例
打开所有单元 关闭所有单元范围 (8)
GraphDistanceMatrix 适用于无向图：
GraphDistanceMatrix[[image]]//MatrixFormGraphDistanceMatrix[[image]]//MatrixFormGraphDistanceMatrix[[image]]//MatrixFormGraphDistanceMatrix[[image]]//MatrixFormGraphDistanceMatrix[[image]]//MatrixFormGraphDistanceMatrix[{1 -> 2, 2 -> 3, 3 -> 1, 3 -> 4, 4 -> 5, 3 -> 5}]//MatrixFormg = GridGraph[{10, 10}];Timing[GraphDistanceMatrix[g][[All, 1]]//Dimensions]使用 GraphDistance 来计算相同的结果花费更多时间：
Timing[Table[GraphDistance[g, 1, v], {v, VertexList[g]}]//Dimensions]GraphDistanceMatrix 适用于大规模图：
g = GridGraph[{10, 10, 10, 10}];Timing[GraphDistanceMatrix[g][[All, 1]]//Dimensions]当只需要一个列，并且图是大规模的，使用 GraphDistance 通常更快：
Timing[Table[GraphDistance[g, 1, v], {v, VertexList[g]}]//Dimensions]选项 (6)
Method (6)
{PetersenGraph[4, 1, VertexShapeFunction -> "Name"], PetersenGraph[4, 1, EdgeWeight -> {4, 0, 3, 1, 3, 2, 7, 8, 5, 2, 1, 6}, VertexShapeFunction -> "Name"]}Table[GraphDistanceMatrix[g]//MatrixForm, {g, %}]GridGraph[{2, 3}, EdgeWeight -> {5, 2, 2, 5, 1, 2, 2}, VertexShapeFunction -> "Name"]GraphDistanceMatrix[%, Method -> "UnitWeight"]//MatrixFormGridGraph[{2, 3}, EdgeWeight -> {5, 2, 2, 5, 1, 2, 2}, VertexShapeFunction -> "Name"]GraphDistanceMatrix[%, Method -> "Dijkstra"]//MatrixForm"FloydWarshall" 可用于边权值含有负数的有向图：
WeightedAdjacencyGraph[(| | | | | | |
| - | - | -- | - | - | - |
| ∞ | 2 | 5 | ∞ | ∞ | ∞ |
| ∞ | ∞ | ∞ | 2 | ∞ | ∞ |
| ∞ | ∞ | ∞ | ∞ | 5 | ∞ |
| ∞ | ∞ | -2 | ∞ | ∞ | 2 |
| ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
| ∞ | ∞ | ∞ | ∞ | 2 | ∞ |), VertexShapeFunction -> "Name", AbsoluteOptions[GridGraph[{2, 3}], VertexCoordinates]]GraphDistanceMatrix[%, Method -> "FloydWarshall"]//MatrixFormWeightedAdjacencyGraph[(| | | | | | |
| - | - | -- | - | - | - |
| ∞ | 2 | 5 | ∞ | ∞ | ∞ |
| ∞ | ∞ | ∞ | 2 | ∞ | ∞ |
| ∞ | ∞ | ∞ | ∞ | 5 | ∞ |
| ∞ | ∞ | -2 | ∞ | ∞ | 2 |
| ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
| ∞ | ∞ | ∞ | ∞ | 2 | ∞ |), VertexShapeFunction -> "Name", AbsoluteOptions[GridGraph[{2, 3}], VertexCoordinates]]GraphDistanceMatrix[%, Method -> "Johnson"]//MatrixForm"Johnson" 对于稀疏图比 "FloydWarshall" 方法更快：
StarGraph[6, EdgeWeight -> RandomReal[{1, 5}, 5]]GraphDistanceMatrix[%, Method -> "Johnson"]//MatrixForm应用 (2)
{a = PetersenGraph[7, 2, VertexSize -> {1 -> Medium}], b = Graph[Range[4], {12, 34}, VertexSize -> {1 -> Medium}], c = Graph[Range[3], {12, 32, 31}, VertexSize -> {1 -> Small}, EdgeStyle -> Arrowheads[Small]]}Table[Max[GraphDistanceMatrix[g][[1]]], {g, {a, b, c}}]对于强连通图，结果与 VertexEccentricity 一致：
Table[VertexEccentricity[g, 1], {g, {a, b, c}}]g = GridGraph[{2, 3, 4}]Max /@ GraphDistanceMatrix[g]% === Table[VertexEccentricity[g, v], {v, VertexList[g]}]属性和关系 (5)
距离矩阵的行和列遵循由 VertexList 给出的顺序：
g = [image];VertexList[g]TableForm[GraphDistanceMatrix[g], TableHeadings -> {c = Style[#, Red]& /@ %, c}]PetersenGraph[5, 2]Diagonal[GraphDistanceMatrix[%]]距离矩阵可以通过使用 GraphDistance 求得：
g = GridGraph[{2, 3}]Table[GraphDistance[g, i, j], {i, VertexList[g]}, {j, VertexList[g]}] == GraphDistanceMatrix[g]在一个连通图中，VertexEccentricity 可以从距离矩阵得到：
g = GridGraph[{3, 4}]GraphDistanceMatrix[g][[VertexIndex[g, 1], All]]//MaxVertexEccentricity[g, 1]属于不同连通分量的两个顶点之间的距离是 Infinity：
g = [image];ConnectedGraphQ[g]GraphDistanceMatrix[g]//MatrixForm可能存在的问题 (2)
矩阵的索引可能与我们所期望的不同，它们并没有与顶点之间的关联：
g = Graph[{23, 12}, EdgeWeight -> {1, 10}, VertexShapeFunction -> "Name"](d = GraphDistanceMatrix[g])//MatrixFormGraphDistance[g, 2, 3] == d[[2, 3]]VertexList[g]通过当调用诸如 Graph 的函数时明确列出顶点，求解该问题：
h = Graph[Range[3], {23, 12}, EdgeWeight -> {1, 10}, VertexShapeFunction -> "Name"]VertexList[h]GraphDistanceMatrix[h]//MatrixFormGraphDistance[h, 2, 3] == %[[2, 3]]"BellmanFord" 不是一个有效的 Method 选项：
g = WeightedAdjacencyGraph[(| | | | | | |
| - | - | -- | - | - | - |
| ∞ | 2 | 5 | ∞ | ∞ | ∞ |
| ∞ | ∞ | ∞ | 2 | ∞ | ∞ |
| ∞ | ∞ | ∞ | ∞ | 5 | ∞ |
| ∞ | ∞ | -2 | ∞ | ∞ | 2 |
| ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
| ∞ | ∞ | ∞ | ∞ | 2 | ∞ |), VertexShapeFunction -> "Name", AbsoluteOptions[GridGraph[{2, 3}], VertexCoordinates]]GraphDistanceMatrix[g, Method -> "BellmanFord"]//MatrixForm
而是使用 "FloydWarshall"、"Johnson" 或者 Method 的默认选项：
GraphDistanceMatrix[g, Method -> "FloydWarshall"]//MatrixFormGraphDistanceMatrix[g, Method -> "Johnson"]//MatrixFormGraphDistanceMatrix[g]//MatrixForm
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 年