5

我正在尝试解决图形问题。图是加权的和无向的。
图表大小：

no. of vertices upto  200,000 
no. of edges upto  200,000

我必须在图中找到给定 2 个节点（S & D）之间的最短路径。我用Dijkstra's algorithm来找这个。
现在的问题是图形经常变化。如果从图中删除特定边，我必须找到 S & D 之间的最短路径。我正在使用 Dijkstra 算法再次计算新路径，方法是将图视为去除边缘后的新图。但是，这种方法太慢了，因为可能有 200,000 条边，我将为每个边删除计算 200,000 次最短路径。
我正在考虑使用任何记忆技术，但无法弄清楚如果从图中删除特定边缘，最短路径可能会完全改变。
//更多细节
源和目的地在整个问题中都是固定的。
每次边缘移除将有多达 200,000 个查询。一次，对于每个测试用例，只从初始图中删除一条边

4

4 回答 4

4

由于没有添加边，因此移除后的最短路径将始终大于（或等于）原始路径。除非删除的边是原始最短路径的一部分，否则结果不会改变。如果它是原始最短路径的一部分，那么再次运行算法是最坏情况的解决方案。

如果您不是在寻找确切的答案，您可以尝试近似的局部方法来填补缺失的边缘。

您可以扩充 Dijkstra 算法以存储允许您在初始搜索期间回溯到特定状态的信息。

这意味着每次在松弛期间最终更改最短路径时，都要记录对数据结构（包括堆）所做的更改。这允许您在第一次运行期间将算法的状态恢复到任何点。

当您删除最短路径上的一条边时，您需要返回到该边松弛之前的点，然后重新启动算法，就好像删除的边从未出现过一样。

于 2012-06-18T06:56:02.797 回答
4

我的建议：

首先使用 Dijkstra 找到从 Source 到 Destination 的最短路径，但同时从 Source 和 Destination 步行（使用负距离数字表示您已经走过的距离目的地有多远），始终扩展最短路径距离（从源或目的地）。一旦遇到具有来自反向节点的值的节点，那么到达该节点的路径是最短的。

然后移除边，如果边不是最短路径的一部分则返回当前已知的最短路径

如果删除的边是最短路径的一部分，则再次执行搜索，已知绝对距离大于（正或负）比被删除的节点中较小的一个。将先前已知的最短路径添加到已知结果中，当从起点步行时为正，从终点走到断路段时为负。现在从该起点开始在两个方向上搜索，如果您点击了一个具有值集（正或负）的节点，或者是先前最短路径的一部分，那么您将找到新的最短路径。

这样做的主要好处是：

  1. 你从源和目的地都走，所以除非你的源节点在边缘，否则你在整体上走的节点更少，并且
  2. 您不会放弃整个搜索结果，即使删除的边是之前最短路径中的第一条边，您只需找到以最短方式重新连接的路径即可。

即使删除的节点是先前已知最短路径的一部分，每次重新计算的性能都将相当可观。

关于它是如何工作的，请看这张图：

        I
       /
  B---E
 /   /   H
A   D   /|
 \ / \ / |
  C---F--G

我们想要从Ato H，为了简单起见，让我们假设每条边都值 1（但它可以是任何东西）

我们从 A 开始：

        I
       /
  B---E
 /   /   H
0   D   /|
 \ / \ / |
  C---F--G

现在将 H 的值设置为从 0 开始：

        I
       /
  B---E
 /   /   (0)
0   D   / |
 \ / \ /  |
  C---F---G

并展开：

        I
       /
  1---E
 /   /   (0)
0   D   / |
 \ / \ /  |
  1---F---G

现在我们扩展下一个最小值，它将是H：

        I
       /
  1---E
 /   /     (0)
0   D     /  |
 \ / \   /   |
  1---(-1)--(-1)

现在我们任意选择B，因为它出现在 之前C，F或者G（它们具有相同的绝对值）：

        I
       /
  1---2
 /   /     (0)
0   D     /  |
 \ / \   /   |
  1---(-1)--(-1)

然后C

        I
       /
  1---2
 /   /        (0)
0   2        /  |
 \ / \      /   |
  1---2 & (-1)--(-1)

现在我们有一个节点，它知道它的正值和负值，因此我们知道它到两者的距离，A并且H由于我们首先扩展最短节点，这一定是最短路径，因此我们可以说从A到的最短路径H是A->C->F->H和成本ABS(2)+ABS(-1) = 3

现在假设我们删除了行 C->F I / 1---2 / / (0) 0 2 / | \ / \ / | 1 2 & (-1)--(-1)

然后，我们删除所有已知值，其绝对值高于 C 和 F 的较小值（在本例中为 1），留下：

        I
       /
  1---E
 /   /     (0)
0   D     /  |
 \ / \   /   |
  1   (-1)--(-1)

现在我们再次像以前一样展开，从B： I / 1---2 / / (0) 0 D / | \ / \ / | 1 (-1)--(-1)

然后C

        I
       /
  1---2
 /   /     (0)
0   2     /  |
 \ / \   /   |
  1   (-1)--(-1)

现在 F：

        I
       /
  1---2
 /   /         (0)
0   2&(-2)    /  |
 \ /    \    /   |
  1      (-1)---(-1)

A因此我们知道从to 到的最短路径H现在是：A->C->D->F->H 和成本ABS(2)+ABS(-2) = 4

这将适用于任意数量的节点、边和边权重，如果您没有更多节点要扩展，那么您将返回“无路由”响应。

您可以通过不重置先前最短路径中节点的节点值来进一步优化它，这样做会失去简单的性质，但不会过于复杂。

在上面的示例中，它最初不会产生影响，但是如果我们随后删除链接会产生影响，因为我们会记住链中其他节点A->C的成本（负数）C

与仅使用单面 Dijkstra 并回滚到移除边缘之前相比的好处如下所示：

        I
       /
  1---E
 /   /   H
0   D   /|
 \ / \ / |
  1   F--G

现在我们将展开B：

        I
       /
  1---2
 /   /   H
0   D   /|
 \ / \ / |
  1   F--G

C：

        I
       /
  1---2
 /   /   H
0   2   /|
 \ / \ / |
  1   F--G

丁：

        I
       /
  1---2
 /   /   H
0   2   /|
 \ / \ / |
  1   3--G

E：

        3
       /
  1---2
 /   /   H
0   2   /|
 \ / \ / |
  1   3--G

F：

        3
       /
  1---2
 /   /   4
0   2   /|
 \ / \ / |
  1   3--4

然后我们将确定现在的路径A->C->D->F->H，它的成本为 4。请注意，我们需要在此处执行 5 个扩展步骤，并将其与我们需要的 3 进行比较。

随着被移除的边缘越来越靠近路径的中间，我们将通过使用双向图行走算法重新计算新路径来获得极大的节省。除非有 50 个节点挂起，但H只有一条路径从A到H其中只有一条从H到 的直接路径，A但有 50 条边连接到A。

鉴于您有大约 200,000 条边，可能多达 200,000 个节点，与我的示例图相比，您可能会看到可观的节省，该示例图只有 9 个节点和 11 条边。这是基于我们正在寻找具有最少节点扩展的算法的想法，因为它们可能大部分计算时间都将用于循环。

于 2012-06-18T14:28:34.243 回答
0

我有个主意：

  • 第一次做 Dijkstra 并记住从 Source 到 Destination 的最短路径的所有边缘。
  • 当您进行删除时，您会检查是否从最短路径中删除了一条边。如果没有结果是一样的。如果是，你做另一个 Dijkstra。

另一个想法：

  • 首先执行 Dijkstra 并为每个顶点记住依赖于该顶点的所有元素。
  • 当您执行删除时，您应该执行诸如拓扑排序之类的操作，并对依赖于您的顶点的所有顶点进行更新，并对这些顶点执行部分 Dikstra。
于 2012-06-18T06:55:32.080 回答
0

如果移除的边缘不是来自最远路径，那么路径将保持不变。否则可能没有好的精确解，因为问题是单调的 - 使用节点 C 从 A 到 B (sp(A, B)) 的最短路径 sp 由所有最短路径组成，使得sp(A, B) = sp(A , C) + sp(C, B)（对于所有 C）。

通过删除一个（非常好的）边缘，您可能会破坏所有这些路径。最好的解决方案（但不准确）可能是使用 Floyd-Warshall 算法来计算所有节点对之间的所有最短路径，并且在从路径中移除边之后尝试使用最短绕行来修复路径。

于 2012-06-18T09:18:32.277 回答