Динамическое обновление кратчайших путей

У меня есть график, на котором мне часто нужно знать все кратчайшие пути (или, скорее, их длину). Поскольку я не хочу их пересчитывать, я сохраняю их в простом массиве и просто извлекаю их оттуда. Однако, поскольку график также может измениться со временем, мне придется пересчитывать их в заданные моменты времени.

На данный момент могут произойти следующие изменения:

• Добавление узла и ребра к нему в граф

• Изменение длины ребра

• Добавление нового ребра графа

• Удаление ребра или удаление узла

Во всех случаях все узлы всегда будут соединены, и все ребра будут иметь положительные веса. Также граф неориентированный. Последовательность операций такова, что все узлы всегда будут из одного и того же компонента графа. Если узел или ребро будут удалены до этого, будут добавлены другие узлы и ребра, так что граф никогда не станет разделенным.

На данный момент я планирую просто выполнить обновления, а затем распространить все изменения через структуру графа. Однако я еще не уверен, как правильно с этим справиться. Как бы вы попытались добиться этих обновлений кэшированной длины.

РЕДАКТИРОВАТЬ :

Как некоторые из вас указали, может потребоваться пересчитать все, когда добавляется узел или изменяется ссылка. Это может быть, например, когда в обновлении изменяются все расстояния. Однако, если я просто распространю изменения по графу и сделаю релаксацию, аналогичную тому, как это делается dijkstras, мне, возможно, придется несколько раз расслаблять один и тот же узел, потому что я могу не выбрать оптимальный порядок. Вопрос будет в том, как упорядочить шаги релаксации, поэтому я стараюсь избегать многократных обновлений настолько хорошо, насколько это возможно.

Не уверен, что это имеет большой смысл без фактической идеи, которую я имею в виду, но я надеюсь, что это проясняет некоторые другие.