最短加权路径的算法 - 经常变化的边

Question

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

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

我需要在图中找到给定两个节点（S和D）之间的最短路径，我正在使用Dijkstra算法来实现这一点。问题在于图经常发生变化。如果从图中删除特定的边，则我必须重新计算S和D之间的最短路径，通过将图视为删除边后的新图，并再次使用Dijkstra算法计算新路径。然而，这种方法太慢了，因为可能有200,000条边，我将为每个边缘删除计算最短路径200,000次。我考虑使用任何记忆技术，但无法确定最短路径是否会完全改变，如果从图中删除特定的边缘。源和目的地在整个问题中保持不变。每个边缘删除最多会有200,000个查询。同时，每个测试用例仅从初始图中删除一个边缘。

- Pranalee

---

在两个最短路径查询之间，图形上进行了多少次更改操作？源和目的地对所有查询都是固定的吗？ - nhahtdh

只是删除边缘还是可以添加边缘呢？我假设如果路径上没有的边被移除，你不会重新计算最短路径。 - Adam

@nhahtdh：我更新了我的问题。源和目的地在整个问题中都是固定的。每次会有多达200,000个查询来删除每个边缘。同时，图中只会删除一条边缘。 - Pranalee

@Adam：不，没有添加边缘。每次从图中仅删除一条边缘。 - Pranalee

图保持连通吗？因为在某个时刻可能会有多个连通组件，如果S在其中一个组件中，而D在另一个组件中，则没有从S到D的路径。 - Mark

@IonescuRobert 不需要在那种情况下。在这种情况下，我应该输出“不可达”。 - Pranalee

Answer 1

我的建议：

首先使用Dijkstra算法从源点到目标点找到最短路径，但同时从源点和目标点开始遍历（使用负距离数表示已经走了多少距离离目标还有多远），始终扩展距离更短的节点（无论是从源节点还是目标节点）。一旦遇到一个节点，它与反向节点之间存在连边，则到达该节点的路径就是最短路径。

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

如果被移除的边是最短路径的一部分，则再次进行搜索，已知绝对距离大于被移除的两个节点之间较小距离（正数或负数）。将以前已知的最短路径作为正数添加到结果中，当从起点行走时为正数，从终点往回走时为负数，直到达到断开的部分。现在从该起点向两个方向搜索，如果遇到一个设置了值（正数或负数）的节点，或者曾经是以前最短路径的一部分，则找到了新的最短路径。

这样做的主要好处是：

1. 您可以同时从源点和目标点开始遍历，因此除非您的源节点位于边界上，否则总共会遍历更少的节点；
2. 即使删除的边是先前最短路径中的第一条边，您也不必放弃整个搜索结果，只需找到重新连接的最短路径即可。

即使被移除的节点是已知的最短路径的一部分，与每次进行蛮力计算相比，性能都会明显提高。

关于其工作原理，请考虑以下图形：

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

我们希望从 A 到达 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。然后我们删除所有已知绝对值高于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到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

D:

        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个边相比，您可能会看到相当大的节省。这基于我们正在寻找具有最少节点扩展的算法，因为它们很可能会花费大量计算时间进行循环。

- Seph

---

看起来你有一点道理，但我没有完全理解 :( - Pranalee

@Pranalee 好的，所以使用Dijkstra算法，每次都先扩展出'最低成本'的节点，采用这种方法，你会扩展出具有最低绝对值成本（忽略负号）的节点；最终，你会扩展出一个节点，它附近的某个节点与你正在计算的节点具有相反的符号，这表明该节点来自相反的方向，同时也是最短路径。如果有机会，我会试图用图形化的方式解释一下。 - Seph

Answer 2

由于没有新增边，因此在去除后的最短路径总是大于（或等于）原始路径。 除非被去除的边是原始最短路径的一部分，否则结果不会改变。 如果它是原始最短路径的一部分，则再次运行算法是最坏情况的解决方案。

如果您不需要精确答案，可以尝试适用于填充缺失边的近似局部方法。

---

您可以增强Dijkstra算法以存储信息，使您能够在初始搜索期间回溯到特定状态。

这意味着每当您在松弛过程中更改最短路径时，请记录对数据结构（包括堆）所做的更改。这使您能够将算法的状态恢复到第一次运行期间的任何点。

当您删除最短路径上的一条边时，您需要回到边被松弛之前的位置，然后重新启动算法，就好像移除的边从未存在过一样。

- VSOverFlow

---

我正在寻找确切的最短距离。 - Pranalee

更多想法：图的预期结构是什么？它是否具有高连通性的聚类，然后在它们之间有弱连接？边缘权重的变化有多大？从S->D枚举所有路径是否可行（可能是因为边的数量与节点数量相同）。还要查看此https://estudogeral.sib.uc.pt/bitstream/10316/7763/1/obra.pdf - VSOverFlow

Answer 3

我有一个想法：

• 第一次进行Dijkstra算法，并记忆从源到目的地的最短路径的所有边。
• 当您进行删除操作时，检查是否删除了最短路径中的边。如果没有，则结果相同。如果是，则执行另一个Dijkstra算法。

另一个想法：

• 首先执行Dijkstra算法，并记住每个顶点所依赖的所有元素。
• 当您执行删除操作时，应该执行类似于拓扑排序的操作，并为所有依赖于您的顶点的顶点进行更新，并使用这些顶点执行部分Dikstra算法。

- Mark

---

我考虑过这个，但是它只会带来一点点优化。而且问题在于它是由边在最短路径中出现的概率驱动的，并不能保证优化结果。 - Pranalee

@Pranalee 如果你将这两个想法结合起来，应该会得到很好的改进。 - Mark

Answer 4

如果被移除的边不是最短路径上的一条，那么路径将保持不变。否则，可能没有好的精确解决方案，因为问题是单调的 - 从A到B的最短路径sp（A，B）使用节点C包括所有最短路径，使得sp（A，B）= sp（A，C）+ sp（C，B）（对于所有C）。

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

- malejpavouk

---

弗洛伊德-沃尔沙算法用于20万个顶点的填充完成时间约为18.06.12345。 - kilotaras