如何以O(n²)复杂度更新含节点间最短路径的n阶矩阵

假设新插入的无向边为(k,l)，其权重为w。原矩阵A存储了图G中所有节点对的最短路径长度（A[i][i]=0，A[i][j]表示i到j的最短路径长度），我们可以通过以下步骤在O(n²)时间内完成更新：

算法步骤 #

1. 遍历所有节点对，更新最短路径
   对于每一对节点(i,j)，新的最短路径只会有两种情况：
   • 不经过新边，保持原长度A[i][j]
   • 经过新边一次，形成两条可能的路径：
     • 路径1：i → k → l → j，长度为A[i][k] + w + A[l][j]
     • 路径2：i → l → k → j，长度为A[i][l] + w + A[k][j]
       因此，对每个(i,j)执行如下更新：

   A[i][j] = min(A[i][j], A[i][k] + w + A[l][j], A[i][l] + w + A[k][j])
   

   由于无向图的对称性（A[i][j] = A[j][i]），也可以只处理i ≤ j的节点对，再同步赋值A[j][i] = A[i][j]，这能减少一半的计算量，但不会改变时间复杂度的阶。

正确性与时间复杂度 #

• 时间复杂度：整个过程仅需两层循环遍历所有n²个节点对，每次循环仅涉及简单的加法和取最小值操作，因此总时间复杂度为O(n²)。
• 正确性：插入新边后，任何经过新边多次的路径（如i→k→l→k→j）必然可以被更短的无重复路径替代（比如i→k→j，原矩阵已经存储了该路径的最短长度）。因此只需考虑经过新边一次的情况，上述更新覆盖了所有可能的更短路径，最终得到的矩阵就是更新后的全源最短路径矩阵。

示例验证 #

假设n=3，原矩阵A为：

A = [
    [0, 5, 10],
    [5, 0, 7],
    [10, 7, 0]
]

插入边(2,3)，权重w=1。执行更新后：

• A[2][3] = min(7, A[2][2]+1+A[3][3], A[2][3]+1+A[2][2]) = min(7, 0+1+0,7+1+0) = 1
• A[1][3] = min(10, A[1][2]+1+A[3][3], A[1][3]+1+A[2][2]) = min(10,5+1+0,10+1+0) =6
  最终更新后的矩阵符合预期。

内容的提问来源于stack exchange，提问作者shedy