У меня есть график, на котором мне часто нужно знать все кратчайшие пути (или, скорее, их длины).Поскольку я не хочу пересчитывать их, я храню их в простом массиве и просто извлекаю их оттуда.Однако, поскольку график может со временем меняться, мне придется пересчитать их в заданные моменты времени.
На данный момент могут произойти следующие изменения:
Добавление узла иребро к нему на график
Изменение длины ребра
Добавление нового ребра графа
Удаление ребра или удаление узла
Во всех случаях все узлы всегда будут связаны, и все ребра имеют положительные веса.Также график является ненаправленным.Последовательность операций такова, что все узлы всегда будут из одного и того же компонента графа.Если узел или ребро будет удалено до того, как будут добавлены другие узлы и ребра, чтобы график никогда не отделился.
Сейчас я планирую просто выполнить обновления, а затем распространить все изменения по графику.состав.Однако я пока не уверен, как правильно с этим справиться.Как бы вы попытались добиться этих обновлений кэшированной длины.
РЕДАКТИРОВАТЬ :
Как некоторые из вас указали, может потребоваться пересчитать все, когда узелдобавлено или ссылка изменена.Это может быть, например, когда все расстояния изменяются при обновлении.Однако, если я просто распространяю изменения по графику и выполняю релаксацию, аналогичную тому, как это делают dijkstras, мне, возможно, придется расслаблять один и тот же узел несколько раз, потому что я могу не выбрать оптимальный порядок.Вопрос заключается в том, как упорядочить этапы релаксации, поэтому я стараюсь избегать как можно большего количества обновлений.
Не уверен, что это имеет смысл, если не иметь в виду реальную идею, но я надеюсь, что это прояснит еще немного.