关于最短路径的非常困难和优雅的问题
very hard and elegant question on shortest path
给定一个带 n 个顶点和 m 个边的加权、连通和有向图 G=(V,E)，并给定一个预先计算的最短路径距离矩阵 S，其中 S是n*n S(i,j)表示从顶点i到顶点j的最短路径的权重。
我们知道只有一个边的权重 (u, v) 发生了变化（增加或减少）。
对于两个特定的顶点s和t我们想更新这两个顶点之间的最短路径长度。
这可以在 O(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 之后将其输入该算法，然后将 'updating' 添加到 BIGNUMBER（我们可以懒惰地构造距离矩阵，因为所有距离要么是 0、inf，要么只是边权重）。这显然是不可能的，因此我们也无法在 O(1) 中解决这个问题。
给定一个带 n 个顶点和 m 个边的加权、连通和有向图 G=(V,E)，并给定一个预先计算的最短路径距离矩阵 S，其中 S是n*n S(i,j)表示从顶点i到顶点j的最短路径的权重。
我们知道只有一个边的权重 (u, v) 发生了变化（增加或减少）。
对于两个特定的顶点s和t我们想更新这两个顶点之间的最短路径长度。
这可以在 O(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 之后将其输入该算法，然后将 'updating' 添加到 BIGNUMBER（我们可以懒惰地构造距离矩阵，因为所有距离要么是 0、inf，要么只是边权重）。这显然是不可能的，因此我们也无法在 O(1) 中解决这个问题。