问加权最短路径-频繁变化边的算法

EN

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

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

您可以增强Dijkstra算法来存储信息，这将允许您在初始搜索期间回溯到特定状态。

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

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

我的建议是：

首先使用Dijkstra查找从源到目的地的最短路径，但同时从源和目的地步行(使用负距离数字来指示您所旅行的目的地有多远)，始终扩展距离最短的路径(从源或目的地)。一旦你遇到一个具有反向节点的值的节点，那么到达该节点的路径就是最短的。

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

如果被移除的边是最短路径的一部分，则再次执行搜索，并且已知绝对距离大于(正或负)被移除的节点中较小的一个。将先前已知的最短路径添加到已知结果中，当从起点遍历时为正，当从末端遍历到断线段时为负。现在从该起点开始两个方向的搜索，如果您遇到的节点设置了值(正或负)，或者是以前最短路径的一部分，那么您将找到新的最短路径。

这样做的主要好处是：

1. 您可以从源节点和目标节点进行遍历，因此除非您的源节点位于某条边，否则您不会放弃整个搜索结果，即使被移除的边是先前最短路径中的第一条边，您也只需找到以最短方式重新连接的路径即可。

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

要了解它的工作原理，请看下面的图表：

        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和costs 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到H的最短路径现在是: A->C->D->F->H，成本为ABS(2)+ABS(-2) = 4

这将适用于任意数量的节点、边和边权重，如果您没有更多的节点可扩展，则返回"No Route“响应。

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

在上面的例子中，一开始不会有什么不同，但如果我们删除链接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条边的示例图相比，您可能会看到相当大的节省。这是基于这样一种想法，即我们正在寻找具有最少节点扩展的算法，因为它们可能会将大部分计算时间花费在循环上。

我有个主意：

第一次做Dijkstra，记住所有的边，对于从Destination.

• When到的最短路径，你做一个删除，检查你是否从最短路径中删除了一条边。如果不是，结果是相同的。如果是，你再做一次Dijkstra。

另一个想法是：

• 首先执行Dijkstra，对于每个顶点，记住依赖于该顶点的所有元素。
• 当您执行移除时，您应该执行类似Topological Sorting的操作，并对依赖于您的顶点的所有顶点执行更新，并使用这些顶点执行部分Dikstra。