最短加权路径算法 - 频繁变换边缘

Question

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

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个查询.每次只对每个测试用例的初始图表中删除一个边缘

Answer 1

我有个主意：

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

另一个想法：

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