我们给了一个加权图G及其最短路径距离的矩阵增量。因此，delta（i，j）表示从i到j的最短路径的权重（i和j是图的两个顶点）。最初会给出包含最短路径值的增量。边缘E的权重突然从W减小到W'。如何更新O（n ^ 2）中的delta（i，j）？（n =图的顶点数）问题不是再次计算具有最佳O（n ^ 3）复杂度的全对最短路径。问题是UPDATING增量，因此我们无需重新计算全对最短路径。
更明确：我们所拥有的只是一个图形及其delta矩阵。增量矩阵仅包含最短路径的值。现在我们要根据图形的变化来更新增量矩阵：减少边缘权重。如何在O（n ^ 2）中更新它？