par*_*ari 4 algorithm graph-theory path-finding shortest-path
我们给了一个加权图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）中更新它？
如果从节点a到节点b的边缘E的权重减小，那么我们可以在恒定时间内更新从节点i到节点j的最短路径长度。从i到j的新的最短路径与旧路径相同，或者包含从a到b的边。如果包含从a到b的边，则其长度为delta(i, a) + edge(a,b) + delta(b, j)。
因此，用O（n ^ 2）算法更新整个矩阵是微不足道的，就像处理无向图的算法一样。
Rob*_*ert -2
阅读 Dijkstra 算法。这就是解决这些最短路径问题的方法，并且无论如何运行时间都小于 O(n^2)。
编辑这里有一些微妙之处。听起来好像为您提供了图中从任何 i 到任何 j 的最短路径，并且听起来您需要更新整个矩阵。对该矩阵进行迭代的次数为 n^2，因为该矩阵是每个节点彼此相连，即 n*n 或 n^2。简单地对增量矩阵中的每个条目重新运行 Dijkstra 算法不会改变此性能等级，因为 n^2 大于 Dijkstra 的 O(|E|+|V|log|V|) 性能。我读得正确吗，还是我记错了大O？
编辑编辑看起来我记错了大O。迭代矩阵将是 n^2，并且每个矩阵上的 Dijkstra 都会产生额外的开销。我不知道在一般情况下如何做到这一点，而不弄清楚 W' 包含在哪些路径中......这似乎意味着应该检查每一对。因此，您要么需要在恒定时间内更新每一对，要么避免检查数组的重要部分。