在數學、計算機科學，尤其是圖論中，距離矩陣是一個方陣（二維數組），包含一組元素之間成對的距離。 根據所涉及的應用，用于定義該矩陣的距離可能是也可能不是度量。 如果有 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