我们得到一个加权图 G 及其最短路径距离的矩阵增量。所以 delta(i,j) 表示从 i 到 j 的最短路径的权重（i 和 j 是图的两个顶点）。最初给出的 delta 包含最短路径的值。突然边缘 E 的权重从 W 减少到 W'。如何在 O(n^2) 中更新 delta(i,j)？（n = 图的顶点数）问题不在于再次计算具有最佳 O(n^3) 复杂度的所有对最短路径。问题是更新增量，因此我们不需要重新计算所有对最短路径。
更明确：我们所拥有的只是一个图和它的增量矩阵。增量矩阵仅包含最短路径的值。现在我们要根据图形的变化来更新 delta 矩阵：降低边权重。如何在 O(n^2) 中更新它？
如果从节点 a 到节点 b 的边 E 的权重减小，那么我们可以在恒定时间内更新从节点 i 到节点 j 的最短路径长度。从 i 到 j 的新最短路径要么与旧路径相同，要么包含从 a 到 b 的边。如果它包含从 a 到 b 的边，那么它的长度是delta(i, a) + edge(a,b) + delta(b, j)。
由此看来，更新整个矩阵的 O(n^2) 算法是微不足道的，处理无向图的算法也是如此。
http://dl.acm.org/citation.cfm?doid=1039488.1039492 http://dl.acm.org.ezp.lib.unimelb.edu.au/citation.cfm?doid=1039488.1039492
尽管他们都考虑增加和减少。增加会使它变得更难。但是，在第 973 页第 3 节中，他们解释了如何在 n*n 中进行仅减少。
不，动态所有对最短路径可以在少于 n n n 的时间内完成。我猜维基百科不是最新的；）
阅读 Dijkstra 的算法。这就是您解决这些最短路径问题的方法，并且无论如何运行时间都小于 O(n^2)。
编辑这里有一些微妙之处。听起来您提供了从图中任何 i 到任何 j 的最短路径，听起来您需要更新整个矩阵。遍历这个矩阵是 n^2，因为矩阵是每个节点彼此相邻，或者 n*n 或 n^2。简单地为增量矩阵中的每个条目重新运行 Dijkstra 算法不会改变这个性能等级，因为 n^2 大于 Dijkstra 的 O(|E|+|V|log|V|) 性能。我是在正确地阅读这篇文章，还是我记错了 big-O？
编辑看起来我记错了big-O。遍历矩阵将是 n^2，并且每个 Dijkstra 将是额外的开销。我不知道在一般情况下如何做到这一点，而没有确切地弄清楚 W' 包含在哪些路径中......这似乎意味着应该检查每一对。因此，您要么需要在恒定时间内更新每一对，要么避免检查数组的重要部分。