距离矩阵

在数学、计算机科学，尤其是图论中，距离矩阵是一个方阵（二维数组），包含一组元素之间成对的距离。 根据所涉及的应用，用于定义该矩阵的距离可能是也可能不是度量。 如果有 N 个元素，则该矩阵的大小为 N×N。 在图论应用中，元素通常被称为点、节点或顶点。

一般来说，距离矩阵是一些图的加权邻接矩阵。 在网络中，将权重分配给弧的有向图，网络的两个节点之间的距离可以定义为连接两个节点的最短路径上的权重总和的最小值。 这个距离函数虽然定义明确，但不是度量标准。 除了需要能够组合和比较它们之外，对权重没有任何限制，因此在某些应用程序中使用负权重。 由于路径是有向的，无法保证对称性，如果存在循环，则距离矩阵可能不是空心的。

上述的代数公式可以通过使用 min-plus 代数获得。 该系统中的矩阵乘法定义如下：给定两个 n × n 矩阵 A = (aij) 和 B = (bij)，它们的距离积 C = (cij) = A ⭑ B 定义为 n × n 矩阵，使得

c i j = min k = 1 n { a i k + b k j } 。 {\displaystyle c_{ij}=\min _{k=1}{n}\{a_{ik}+b_{kj}\}。}

请注意，未直接连接的非对角线元素需要设置为无穷大或合适的大值，以便 min-plus 操作正常工作。 这些位置中的零将被错误地解释为没有距离、成本等的边缘。

如果 W 是包含图的边权重的 n × n 矩阵，则 Wk（使用此距离积）使用长度最多为 k 条边的路径给出顶点之间的距离，Wn 是图的距离矩阵。

n 个顶点上的任意图 G 可以建模为 n 个顶点上的加权完全图，方法是为对应于 G 的边的完整图的每条边分配权重 1，为所有其他边分配权重 0。 这个完整图的 W 是 G 的邻接矩阵。G 的距离矩阵可以从 W 如上所述计算，但是，通过通常的矩阵乘法计算的 Wn 仅编码长度恰好为 n 的任意两个顶点之间的路径数。

在许多应用中，距离矩阵形式主义的价值在于距离矩阵如何明确地编码度量公理，以及它如何有助于使用线性代数技术。 也就是说，如果 M = (xij) 且 1 ≤ i，j ≤ N 是度量距离的距离矩阵，则

• 主对角线上的元素全为零（即矩阵为空心矩阵），即xii = 0 for all 1 ≤ i ≤ N,
• 所有非对角线元素都是正数（xij > 0 if i ≠ j），（即非负矩阵），
• 矩阵是对称矩阵(xij = xji)，并且
• 对于任何 i 和 j，对于所有 k（三角不等式）xij ≤ xik + xkj。 这可以用热带矩阵乘法表示

当距离矩阵满足前三个公理（使其成为半度量）时，它有时被称为预距离矩阵。 可以嵌入到欧氏空间中的预距离矩阵称为欧氏距离矩阵。

度量距离矩阵的另一个常见示例出现在编码理论中，当在块代码中，元素是字母表上固定长度的字符串，并且它们之间的距离由汉明距离度量给出。 距离矩阵中最小的非零项衡量代码的纠错和检错能力。

加性距离矩阵是生物信息学中用于构建系统发育树的一种特殊类型的矩阵。 设 x 是两个物种 i 和 j 之间的最低共同祖先，我们期望 Mij = Mix + Mxj。 这就是附加指标的来源。 一组物种 S 的距离矩阵 M 被认为是可加的，当且仅当存在 S 的系统发育 T 时：

• T 中的每条边 (u,v) 都与一个正权重 duv 相关联
• 对于每个 i,j ∈ S，Mij 等于 T 中从 i 到 j 的路径上的权重之和

对于这种情况，M 称为加法矩阵，T 称为加法树。

超距离矩阵被定义为模拟恒定分子钟的加性矩阵。 它用于构建系统发育树。 如果存在树 T 使得矩阵 M 被称为超矩阵：

• Mij 等于 T 中 i 到 j 沿路径的边权值之和
• 树的根可以被识别为 wi