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

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) 内解决这个问题。