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

Материал из WEGA
Перейти к навигации Перейти к поиску

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

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

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

delete(u, v): удаляет дугу (u ,v) из графа;

distance(x,y): возвращает значение расстояния от вершины x до вершины y;

path(x,y): возвращает кратчайший путь между вершинами x и y, если такой существует.

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

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

Простое решение этой задачи заключается в реконструкции кратчайших путей с нуля после каждого удаления при помощи лучшего статического APSP-алгоритма, что позволит выполнять запросы о расстоянии и пути за оптимальное время. Лучший из известных статических APSP-алгоритмов для графа с произвольными действительными весами дуг выполняется за время [math]\displaystyle{ O(mn + n^2 log \; log n) }[/math], где m – количество дуг, а n – количество вершин графа [13]. В худшем случае это составляет [math]\displaystyle{ O(n^3) \; }[/math]. Фредман [6] и позднее Такаока [19] показали, как разрушить кубический барьер; лучшая асимптотическая граница решения APSP-задачи найдена Такаокой и составляет [math]\displaystyle{ O(n^3 \sqrt{log log n/log n}) }[/math].

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

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

Первый декрементный алгоритм с предположительно меньшим временем работы по сравнению с перевычислением с нуля предложила Валери Кинг для специального случая графов с целочисленными весами дуг величиной не более C; ее алгоритм способен обновлять кратчайшие пути в графе после серии из [math]\displaystyle{ \Omega (n^2) \; }[/math] удалений, где каждое удаление производится за амортизированное время [math]\displaystyle{ O(C \cdot n^2 \; ) }[/math] [9]. Позднее Деметреску и Италиано показали, как обрабатывать графы с действительными неотрицательными весами дуг за амортизированное время [math]\displaystyle{ O(n^2 \; log n) \; }[/math] на одно удаление [2] в последовательности из [math]\displaystyle{ \Omega (m/n) \; }[/math] операций. Оба алгоритма работают и в более общем случае, когда дуги не удаляются из графа, но их вес увеличивается с каждым обновлением. Более того, поскольку эти алгоритмы явно обновляют кратчайшие пути после каждого удаления, ответы на запросы выдаются за оптимальное время в любой момент последовательности операций.

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

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

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

Теорема 1. Если кратчайшие пути являются уникальными в графе, то количество путей, которые становятся кратчайшими или перестают быть кратчайшими после каждого удаления дуги, равно [math]\displaystyle{ O(n^2) \; }[/math] в результате амортизации по [math]\displaystyle{ \Omega(m/n) \; }[/math] операциям обновления.

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

Теорема 2. Рассмотрим граф, содержащий n вершин и изначально m дуг, в котором последовательно производится [math]\displaystyle{ \Omega(m/n) \; }[/math] удалений дуг. Если кратчайшие пути являются уникальными, а веса дуг – неотрицательными, то каждую операцию удаления можно выполнить за амортизированное время [math]\displaystyle{ O(n^2 \; logn) }[/math], каждый запрос о расстоянии – за время [math]\displaystyle{ O(1) \; }[/math] в худшем случае, а каждый запрос о пути – за время [math]\displaystyle{ O(\ell ) \; }[/math] в худшем случае, где [math]\displaystyle{ \ell \; }[/math] – число вершин в отмеченном кратчайшем пути. Объем требуемой памяти составляет [math]\displaystyle{ O(mn) \; }[/math].

Применение

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

Эффективная реализация декрементного алгоритма на языке C доступна по адресу http://www.dis.uniroma1.it/~demetres/experim/dsp.

См. также

Литература

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)

Источник — http://pco.iis.nsk.su/wega/index.php?title=Декрементный_алгоритм_нахождения_кратчайших_путей_между_всеми_парами&oldid=13051