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

Question

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

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

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

Answer 1

由于没有加边，去掉后的最短路径总是会大于(或等于)原来的。除非删除的边是原来最短路径的一部分，否则结果不会改变。如果是原来最短路径的一部分，那么再次运行算法就是最坏情况的解决方案。

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

---

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

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

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