Декрементный алгоритм нахождения кратчайших путей между всеми парами

Ключевые слова и синонимы: алгоритм нахождения кратчайших путей между всеми парами (только удаление)

Постановка задачи

Динамический алгоритм на графе поддерживает заданное свойство P графа, подверженного динамическим изменениям – таким как вставка дуги, удаление дуги и обновление веса дуги. Динамический алгоритм должен быстро обрабатывать запросы о свойстве T, а также выполнять операции обновления быстрее, чем вычислять то же самое с нуля при помощи самого быстрого статического алгоритма. Алгоритм является полностью динамическим, если он поддерживает как вставку дуг, так и удаление дуг. Частично динамический алгоритм поддерживает либо вставку, либо удаление дуг; инкрементный алгоритм поддерживает только вставку дуг, декрементный – только удаление. Далее рассматривается декрементная версия алгоритма нахождения кратчайших путей между всеми парами (APSP), которая включает поддержку ориентированного графа с дугами, имеющими вещественные веса, и выполнение последовательности следующих операций в различном порядке: delete(u, v): удаляет дугу (u ,v) из графа; distance(x,y): возвращает значение расстояния от вершины x до вершины y; path(x,y): возвращает кратчайший путь между вершинами x и y, если такой существует.

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

История задачи

Простое решение этой задачи заключается в реконструкции кратчайших путей с нуля после каждого удаления при помощи лучшего статического APSP-алгоритма, что позволит выполнять запросы о расстоянии и пути за оптимальное время. Лучший из известных статических APSP-алгоритмов для графа с произвольными действительными весами дуг выполняется за время O(mn + n2 loglog n), где m – количество дуг, а n – количество вершин графа [13]. В худшем случае это составляет Q(n3). Фредман [ ] и позднее Такаока [19] показали, как разрушить кубический барьер; лучшая асимптотическая граница решения APSP-задачи найдена Такаокой и составляет O(n3 ploglog n/log n).

Еще одним простым решением является ответ на запросы путем поточечного вычисления кратчайших путей, без необходимости обновления кратчайших путей после каждого удаления дуги. Это можно выполнить при помощи алгоритма Дейкстры [ ] за время O(m + n log n), используя фибоначчиевы кучи из метода Фредмана-Тарьяна [ ]. Подобный подход позволяет давать ответы на запросы за время O(m + n log n) в худшем случае, тогда как обновления выполняются за оптимальное время.

Динамические алгоритмы вычисления кратчайших путей разрабатывались уже давно; первые статьи по этой теме датированы 1967 годом [11,12,17]. В 1985 Ивэн и Гацит [ ] представили алгоритмы вычисления кратчайших путей в ориентированных графах с произвольными действительными весами. Время работы алгоритма для удаления дуг в худшем случае сравнимо с вычислением APSP с нуля. Рамалингам и Репс [15, 16], а также Фригиони и коллеги [7, 8] рассматривали динамические алгоритмы вычисления кратчайших путей для графа с действительными весами на базе другой модели; время исполнения алгоритма рассматривалось с точки зрения изменения выходного графа, а не в терминах размера входного графа (сложность в виде выходного ограничения). Время работы динамических алгоритмов с выходным ограничением в худшем случае также сравнимо с вычислением APSP с нуля.

Первый декрементный алгоритм с предположительно меньшим временем работы по сравнению с перевычислением с нуля предложила Валери Кинг для специального случая графов с целочисленными весами дуг величиной не более C; ее алгоритм способен обновлять кратчайшие пути в графе после серии из Q{n2) удалений, где каждое удаление производится за амортизированное время O(C ■ n2) [ ]. Позднее Деметреску и Италиано показали, как обрабатывать графы с действительными неотрицательными весами дуг за амортизированное время O(n2 log n) на одно удаление [2] в последовательности из Q{mln) операций. Оба алгоритма работают и в более общем случае, когда дуги не удаляются из графа, но их вес увеличивается с каждым обновлением. Более того, поскольку эти алгоритмы явно обновляют кратчайшие пути после каждого удаления, ответы на запросы выдаются за оптимальное время в любой момент последовательности операций.

Основные результаты

Декрементный APSP-алгоритм, разработанный Деметреску и Италиано, основывается на понятии локально кратчайших путей [2]. Путь является локально кратчайшим в графе, если все его собственные подпути являются кратчайшими путями.

Согласно свойству оптимальности подструктуры, кратчайший путь является локально кратчайшим. Основная идея алгоритма заключается в том, чтобы хранить информацию о локально кратчайших путях в графе, в котором планируется удаление дуг. Теорема 1, приведенная в [], ограничивает число изменений в множестве локально кратчайших путей, связанных с удалением дуг.

Теорема 1. Если кратчайшие пути являются уникальными в графе, то количество путей, которые становятся кратчайшими или перестают быть кратчайшими после каждого удаления дуги, равно O(n2) в результате амортизации по Q{mln) операциям обновления.

Результат теоремы 1 является чисто комбинаторным; он предполагает, что кратчайшие пути уникальны в графе. Последнее можно легко установить при помощи любой согласованной стратегии разрешения спорных ситуаций (см., например, [ ]). Можно разработать алгоритм, включающий только удаления, который будет тратить только O(log n) времени на одно изменение в множестве локально кратчайших путей, используя простую модификацию алгоритма Дейкстры []. Поскольку, согласно теореме 1, амортизированное число изменений ограничено O(n2), из этого следует:

Теорема 2. Рассмотрим граф, содержащий n вершин и изначально m дуг, в котором последовательно производится Q(mln) удалений дуг. Если кратчайшие пути являются уникальными, а веса дуг – неотрицательными, то каждую операцию удаления можно выполнить за амортизированное время O(n2logn), каждый запрос о расстоянии – за время O(1) в худшем случае, а каждый запрос о пути – за время O(1) в худшем случае, где I – число вершин в отмеченном кратчайшем пути. Объем требуемой памяти – O(mn).

Применение

В число сценариев применения динамических алгоритмов нахождения кратчайших путей входят оптимизация сетей [ ], форматирование документов [10], маршрутизация в системах коммуникации, робототехника, инкрементная компиляция, системы управления информацией о дорожном движении [18] и анализ потоков данных. Полный обзор реальных областей применения динамических алгоритмов нахождения кратчайших путей приведен в [14].

Эффективная реализация декрементного алгоритма на языке C доступна по адресу [1].

См. также

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

Литература

1. Ahuja, R., Magnanti, T., Orlin, J.: Network Flows: Theory, Algorithms and Applications. Prentice Hall, Englewood Cliffs, NJ (1993) 2. Demetrescu, C., Italiano, G.: A new approach to dynamic all pairs shortest paths. J. Assoc. Comp. Mach. 51,968-992 (2004) 3. Dijkstra, E.: A note on two problems in connexion with graphs. Numerische Mathematik 1,269-271 (1959) 4. Even, S., Gazit, H.: Updating distances in dynamic graphs. Meth. Op. Res. 49, 371-387(1985) 5. Fredman, M., Tarjan, R.: Fibonacci heaps and their use in improved network optimization algorithms. J. ACM 34, 596-615 (1987) 6. Fredman, M.L.: New bounds on the complexity of the shortest path problems. SIAM J. Comp. 5(1), 87-89 (1976) 7. Frigioni, D., Marchetti-Spaccamela,A., Nanni, U.: Semi-dynamic algorithms for maintaining single source shortest paths trees. Algorithmica 22, 250-274 (1998) 8. Frigioni, D., Marchetti-Spaccamela, A., Nanni, U.: Fully dynamic algorithms for maintaining shortest paths trees. J. Algorithm 34,351-381 (2000) 9. King, V.: Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. In: Proc. 40th IEEE Symposium on Foundations of Computer Science (FOCS'99), pp. 81-99. IEEE Computer Society, New York, USA (1999) 10. Knuth, D., Plass, M.: Breaking paragraphs into lines. Software-Practice Exp. 11,1119-1184 (1981) 11. Loubal, P.: A network evaluation procedure. Highway Res. Rec. 205,96-109(1967) 12. Murchland, J.: The effect of increasing or decreasing the length of a single arc on all shortest distances in a graph, tech. rep., LBS-TNT-26, London Business School. Transport Network The ory Unit, London, UK (1967) 13. Pettie, S.: A new approach to all-pairs shortest paths on real-weighted graphs. Theor. Comp. Sci. 312,47-74 (2003) special issue of selected papers from ICALP (2002) 14. Ramalingam, G.: Bounded incremental computation. Lect. Note Comp. Sci. 1089 (1996) 15. Ramalingam, G., Reps, T.: An incremental algorithm for a generalization of the shortest path problem. J. Algorithm 21, 267-305(1996) 16. Ramalingam, G., Reps, T.: On the computational complexity of dynamic graph problems. Theor. Comp. Sci. 158, 233-277 (1996) 17. Rodionov, V.: The parametric problem of shortest distances. USSR Comp. Math. Math. Phys. 8, 336-343 (1968) 18. Schulz, F., Wagner, D., Weihe, K.: Dijkstra's algorithm on-line: an empirical case study from public railroad transport. In: Proc. 3rd Workshop on Algorithm Engineering (WAE'99), pp. 110-123. Notes in Computer Science 1668. London, UK (1999) 19. Takaoka, T.: A new upper bound on the complexity of the all-pairs shortest path problem. Inf. Proc. Lett. 43,195-199 (1992)