Как пересчитать все пары кратчайших путей в режиме онлайн, если узлы удаляются?

Question

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

С простой модификацией алгоритма Флойда-Варшалла мы можем вычислить кратчайшие пути между всеми парами. Эти пути могут храниться в таблице, где shortest[i][j] содержит индекс следующего узла на кратчайшем пути между i и j (или значением NULL, если пути нет). Алгоритм требует O (n³) времени для построения таблицы, а каждый запрос shortest(i,j) принимает O (1). К сожалению, мы должны перезапускать этот алгоритм после каждого удаления.

Другая альтернатива - запускать поиск по графику для каждого запроса. Таким образом, каждое удаление занимает нулевое время для обновления вспомогательной структуры (потому что ее нет), но каждый запрос занимает время O (E).

Какой алгоритм можно использовать, чтобы «сбалансировать» запрос и время обновления для проблемы кратчайших путей для всех пар при удалении узлов графа?

Answer 1

Как упоминалось goran , вам нужно только пересчитать те кратчайшие пути, которые содержали узел, который был удален за это время. Итак, я бы сделал следующее:

1. Рассчитать все кратчайшие пути, используя алгоритм Флойда-Варшалла Это O ( n ³ ).
2. Создайте индекс, который назначает индексы вершин списку кратчайших путей, в которых участвует вершина. (Другими словами, для каждой вершины i он дает вам список (j, k ) пар st i присутствует в кратчайшем пути между вершиной j и k ). Это O ( n ² d ) (где d - диаметр графа), так как вы должны проходить по каждой вершине в каждом из кратчайших путей, определенных в предыдущий шаг, и есть n ² таких кратчайших путей.
3. После удаления вершины посмотрите список затронутых кратчайших путей из индекса, созданного на шаге 2, и пересчитайте их. Так как здесь вам не нужны все кратчайшие пути, и я предполагаю, что затронуты только несколько узлов, вам, вероятно, лучше использовать поиск в нескольких широтах, а это O ( m + n ) где m - количество ребер.

Answer 2

Я отвечу на предполагаемый неуниверсальный вариант задачи, где график - это дорожная сеть. Это кажется мне одним из случаев, когда теоретические оценки на произвольных графах менее интересны.

Одними из лучших подходов для поиска кратчайшего пути являются маршрутизация на шоссе и на транзитном узле. (описано в диссертации Доминика Шульта ). Структура ускорения может быть построена достаточно быстро (~ 15 минут для HNR всей Европы), и она поддерживает постепенные обновления. Интересно то, что время запроса случайных запросов составляет около 1 мс, а таблицы расстояний для всех пар можно рассчитать всего за 0,2 с на запись. Что еще более интересно, так это масштабирование производительности запросов, данные свидетельствуют о том, что масштабирование является суб-логарифмическим / почти постоянным по размеру графика. Маршрутизация транзитных узлов еще быстрее при случайных запросах 4.3us. Увы, у меня нет никакой информации об обновляемости структуры данных. Интуитивно понятно, что постепенное обновление не должно быть слишком сложным.

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

Answer 3

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

Тривиальным решением вашей проблемы будет добавление информации о избыточных путях, например, у вас может быть второй кратчайший путь для каждого из узлов на кратчайшем пути. Это не уменьшает время вычислений, но кэширует его (это также увеличивает требования к хранилищу с коэффициентом n, где n - среднее число узлов для удаления одного узла, с коэффициентом n * (n-1) для 2 узлов избыточность ... и с коэффициентом n! для полной избыточности, а также увеличивает время первоначальной сборки на тот же коэффициент, а также увеличивает время, необходимое для добавления узлов)

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