Инкрементальный алгоритм Дейкстры или кратчайшего пути?

Question

У меня есть начальный ориентированный граф G, из которого я время от времени удаляю ребра (никогда не добавляю новые). Я не удаляю узлы (хотя некоторые из них могут быть отключены). Есть ли способ эффективно пересчитывать кратчайшие пути без запуска Dijkstra с нуля? Начальный узел никогда не изменяется.

Если нет инкрементной версии алгоритма Дейкстры, какой-то другой алгоритм будет в порядке. Но я не могу использовать A * (я помню, что есть инкрементная версия), потому что у меня нет никакой эвристики, чтобы знать, насколько я далеко от цели.

Спасибо

Answer 1

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

Остальные узлы не нуждаются в обновлении. Если вы удаляете края, вы можете сделать дорожки длиннее.

Пробегайте все ребра и если источник не нуждается в обновлении, но пункт назначения добавляет адресат в очередь приоритета Dijkstra. После того, как вы сделали это, запустите обычный алгоритм Дейкстры, чтобы выяснить новые затраты.

Если вы удалите одну из ссылок из источника, вы все равно можете запустить всю дикстра. Вероятно, это полезно только в том случае, если вы не пытаетесь удалить использованные ссылки (так как есть хороший шанс, что ссылка удалена не используется) или если вы удалите ссылку, чтобы она находилась далеко от источника (так вам нужно только для обновления нескольких узлов).