algorithm - 关于最短路径的非常困难和优雅的问题

Question

给定一个加权、连通和有向图 G=(V,E)与 n顶点和 m边，并给出预先计算的最短路径距离矩阵 S哪里S是 n*n S(i,j)表示从顶点开始的最短路径的权重 i到顶点 j .
我们只知道一条边的权重 (u, v)改变(增加或减少)。
对于两个特定的顶点 s和 t我们要更新这两个顶点之间的最短路径长度。
这可以在 O(1). 中完成
这怎么可能？这个答案的诀窍是什么？

Answer 1

你当然可以减少。我假设 S将始终指旧的距离。让 l是 (u, v) 之间的新距离.检查是否

S(s, u) + l + S(v, t) < S(s, t)

如果是，则左侧是 s 之间的新最佳距离和 t .

增加是不可能的。考虑下图(红色边的权重为零):

假设 m是这里的最小权重边，除了 (u, v)这曾经是较低的。现在我们更新 (u, v)到一些重量 l > m .这意味着我们必须找到 m找到新的最佳长度。
假设我们可以在 O(1) 时间内完成此操作。那么这意味着我们可以在 O(1) 时间内通过将 (u, v) 添加到该算法中来找到任何数组的最小值。带重量 -BIGNUMBER然后将其“更新”为 BIGNUMBER (我们可以懒惰地构造距离矩阵，因为所有距离都是 0 、 inf 或只是边缘权重)。这显然是不可能的，因此我们也无法在 O(1) 中解决这个问题。