алгоритм поиска кратчайшего взвешенного пути - часто меняющиеся ребра

Я пытаюсь решить задачу о графе. Граф взвешен и ненаправлен.
Размер графика:

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

Мне нужно найти кратчайший путь между заданными двумя узлами (S и D) на графике. Я использую алгоритм Дейкстры, чтобы найти это.
Теперь проблема в том, что график часто меняется. Мне нужно найти кратчайший путь между S и D, если конкретное ребро удалено из графа. Я снова вычисляю новый путь, используя алгоритм Дейкстры, рассматривая граф как новый граф после удаления ребра. Однако этот подход слишком медленный, так как может быть 200 000 ребер, и я буду вычислять кратчайший путь 200 000 раз для каждого удаления ребра.
Я думал об использовании какой-либо техники запоминания, но не смог понять, поскольку кратчайший путь может полностью измениться, если из графа будет удалено определенное ребро.
//подробнее
Источник и место назначения фиксируются на протяжении всей задачи.
На каждое удаление ребра будет отправлено до 200 000 запросов. за раз из исходного графа для каждого теста удаляется только одно ребро