如果一条边权重减少，则更新最短路径距离矩阵
我们得到一个加权图 G 及其最短路径距离的矩阵 delta。因此 delta(i,j) 表示从 i 到 j 的最短路径的权重（i 和 j 是图的两个顶点）。 最初给出的 delta 包含最短路径的值。突然，边 E 的权重从 W 减少到 W'。如何在 O(n^2) 中更新 delta(i,j)？ (n=图的顶点数) 问题不在于再次计算具有最佳 O(n^3) 复杂度的全对最短路径。问题是更新增量，这样我们就不需要重新计算所有对的最短路径。
更明确的是：我们拥有的只是一个图及其增量矩阵。增量矩阵仅包含最短路径的值。现在我们要根据图形的变化更新增量矩阵：边权重减少。如何在 O(n^2) 内更新它？
We are given a weighed graph G and its Shortest path distance's matrix delta. So that delta(i,j) denotes the weight of shortest path from i to j (i and j are two vertexes of the graph).
delta is initially given containing the value of the shortest paths. Suddenly weight of edge E is decreased from W to W'. How to update delta(i,j) in O(n^2)? (n=number of vertexes of graph)
The problem is NOT computing all-pair shortest paths again which has the best O(n^3) complexity. the problem is UPDATING delta, so that we won't need to re-compute all-pair shortest paths.
More clarified : All we have is a graph and its delta matrix. delta matrix contains just value of the shortest path. now we want to update delta matrix according to a change in graph: decreased edge weight. how to update it in O(n^2)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
如果从节点a到节点b的边E的权重减小，那么我们可以在常数时间内更新从节点i到节点j的最短路径长度。从 i 到 j 的新最短路径要么与旧路径相同，要么包含从 a 到 b 的边。如果它包含从 a 到 b 的边，则其长度为 delta(i, a) + edge(a,b) + delta(b, j) 。
由此可见，更新整个矩阵的 O(n^2) 算法是微不足道的，处理无向图的算法也是如此。
If edge E from node a to node b has its weight decreased, then we can update the shortest path length from node i to node j in constant time. The new shortest path from i to j is either the same as the old one or it contains the edge from a to b. If it contains the edge from a to b, then its length is
delta(i, a) + edge(a,b) + delta(b, j).From this the O(n^2) algorithm to update the entire matrix is trivial, as is the one dealing with undirected graphs.
http://dl.acm.org/itation.cfm?doid=1039488.1039492
http://dl.acm.org.ezp .lib.unimelb.edu.au/itation.cfm?doid=1039488.1039492
虽然他们都考虑了增加和减少。增加就会变得更困难。
不过，在第一个第 973 页第 3 节中，他们解释了如何在 n*n 中进行仅减少。
不，动态所有对最短路径可以在不到 nnn 的时间内完成。我猜维基百科不是最新的；）
http://dl.acm.org/citation.cfm?doid=1039488.1039492
http://dl.acm.org.ezp.lib.unimelb.edu.au/citation.cfm?doid=1039488.1039492
Although they both consider increase and decrease. Increase would make it harder.
On the first one, though, page 973, section 3 they explain how to do a decrease-only in n*n.
And no, the dynamic all pair shortest paths can be done in less than nnn. wikipedia is not up to date I guess ;)
阅读 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' 包含在哪些路径中......这似乎意味着应该检查每一对。因此，您要么需要在恒定时间内更新每一对，要么避免检查数组的重要部分。
Read up on Dijkstra's algorithm. It's how you do these shortest-path problems, and runs in less than O(n^2) anyway.
EDIT There are some subtleties here. It sounds like you're provided the shortest path from any i to any j in the graph, and it sounds like you need to update the whole matrix. Iterating over this matrix is n^2, because the matrix is every node by every other, or n*n or n^2. Simply re-running Dijkstra's algorithm for every entry in the delta matrix will not change this performance class, since n^2 is greater than Dijkstra's O(|E|+|V|log|V|) performance. Am I reading this properly, or am I misremembering big-O?
EDIT EDIT It looks like I am misremembering big-O. Iterating over the matrix would be n^2, and Dijkstra's on each would be an additional overhead. I don't see how to do this in the general case without figuring out exactly which paths W' is included in... this seems to imply that each pair should be checked. So you either need to update each pair in constant time, or avoid checking significant parts of the array.