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

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

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

Задача заключается в эффективной поддержке информации о кратчайших путях между всеми парами в динамически меняющемся графе. Эта задача исследовалась еще с 60-х годов [17, 18, 20]; она играет важнейшую роль во множестве приложений, включая такие области, как оптимизация и маршрутизация сетей, системы управления информацией о дорожном движении, базы данных, компиляторы, сбор мусора, интерактивные системы верификации, робототехника, анализ потоков данных и форматирование документов.


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


В задаче нахождения кратчайших путей между всеми парами (APSP) необходимо поддерживать ориентированный граф G = (V, E) с дугами, имеющими вещественные веса, и выполнение последовательности следующих операций в различном порядке:

Update(x, y, w): обновление веса дуги (x, y) с присвоением вещественного значения w; эта операция включает в качестве специальных случаев вставку дуги (если вес меняется с [math]\displaystyle{ + \mathcal{1} }[/math] на w < [math]\displaystyle{ + \mathcal{1} }[/math]) и удаление дуги (если вес устанавливается равным w = [math]\displaystyle{ + \mathcal{1} }[/math]);

Distance(x, y): возвращает кратчайшее расстояние от x до y.

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


Более формально эту задачу можно определить следующим образом.

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

Дано: взвешенный ориентированный граф G = (V, E) и вышеописанная последовательность операций [math]\displaystyle{ \sigma\ }[/math].

Требуется: найти матрицу D, такую, что ячейка матрицы D[x, y] хранит расстояние между вершинами x и y на протяжении всей последовательности операций.


Пусть n и m обозначают число вершин и дуг графа G, соответственно. Деметреску и Итальяно [3] предложили новый подход к решению динамических задач нахождения путей, основанный на поддержке классов путей, характеризующихся локальными свойствами – то есть свойствами, выполняющимися для всех подходящих подпутей, даже если они не обязательно выполняются для целых путей. Авторы показали, что этот подход может сыграть важнейшую роль в процессе динамической поддержки кратчайших путей.

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

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

Используя тот же подход, Торуп [22] показал, как можно несколько улучшить время исполнения:

Теорема 2. Полностью динамическая задача нахождения кратчайших путей может быть решена за амортизированное время [math]\displaystyle{ O(n^2(log \; n + log^2 (m/n))) }[/math] на одно обновление при помощи выполнения любой последовательности операций. Объем требуемой памяти составляет O(mn).

Применение

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


Открытые вопросы

Недавние исследования в области динамических алгоритмов нахождения кратчайших путей поставили новые и весьма интересные вопросы. Можно ли уменьшить объем памяти, необходимой динамическому алгоритму нахождения кратчайших путей, до O(n2)? Возможно, еще более важный вопрос заключается в том, можно ли эффективно решить полностью динамическую задачу достижимости и нахождения кратчайших путей с единственным источником на графах общего вида? Наконец, существуют ли техники общего вида, позволяющие сделать полностью динамическими алгоритмы, использующие только приращение? Подобные техники широко использовались в случае полностью динамических алгоритмов на неориентированных графах [11, 12, 13].


Экспериментальные результаты

Основательное эмпирическое исследование описанных здесь алгоритмов можно найти в статье Деметреску и Итальяно [4].


См. также


Литература

1. Ausiello, G., Italiano, G.F., Marchetti-Spaccamela, A., Nanni, U.: Incremental algorithms for minimal length paths. J. Algorithm 12(4),615-38(1991)

2. Demetrescu, C.: Fully Dynamic Algorithms for Path Problems on Directed Graphs. Ph.D. thesis, Department of Computer and Systems Science, University of Rome "La Sapienza", Rome (2001)

3. Demetrescu, C., Italiano, G.F.: A new approach to dynamic all-pairs shortest paths. J. Assoc. Comp. Mach. 51(6), 968-992 (2004)

4. Demetrescu, C., Italiano, G.F.: Experimental analysis of dynamic all pairs shortest path algorithms. ACM Trans. Algorithms 2(4), 578-601 (2006)

5. Demetrescu, C., Italiano, G.F.: Trade-offs for fully dynamic reachability on dags: Breaking through the O(n2) barrier. J. Assoc. Comp. Mach. 52(2), 147-156 (2005)

6. Demetrescu, C., Italiano, G.F.: Fully Dynamic All Pairs Shortest Paths with Real Edge Weights. J. Comp. Syst. Sci. 72(5), 813-837 (2006)

7. Even, S., Gazit, H.: Updating distances in dynamic graphs. Method. Oper. Res. 49, 371 -387 (1985)

8. Frigioni, D., Marchetti-Spaccamela,A., Nanni, U.: Semi-dynamic algorithms for maintaining single source shortest paths trees. Algorithmica 22(3), 250-274 (1998)

9. Frigioni, D., Marchetti-Spaccamela, A., Nanni, U.: Fully dynamic algorithms for maintaining shortest paths trees. J. Algorithm 34,351-381 (2000)

10. Henzinger, M., King, V.: Fully dynamic biconnectivity and transitive closure. In: Proc. 36th IEEE Symposium on Foundations of Computer Science (FOCS'95). IEEE Computer Society, pp. 664-672. Los Alamos (1995)

11. Henzinger, M., King, V.: Maintaining minimum spanning forests in dynamic graphs. SIAM J. Comp. 31 (2), 364-374 (2001)

12. Henzinger, M.R., King, V.: Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J. ACM 46(4),502-516(1999)

13. Holm, J., de Lichtenberg, K.,Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM 48, 723-760 (2001)

14. 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). IEEE Computer Society pp. 81-99. Los Alamos (1999)

15. King, V., Sagert, G.: A fully dynamic algorithm for maintaining the transitive closure. J. Comp. Syst. Sci. 65(1), 150-167 (2002)

16. King, V., Thorup, M.: A space saving trick for directed dynamic transitive closure and shortest path algorithms. In: Proceedings of the 7th Annual International Computing and Combinatorics Conference (COCOON). LNCS, vol. 2108, pp. 268-277. Springer, Berlin (2001)

17. Loubal, P.: A network evaluation procedure. Highway Res. Rec. 205,96-109(1967)

18. Murchland, J.: The effect of increasing or decreasing the length of a single arc on all shortest distances in a graph. Technical report, LBS-TNT-26, London Business School, Transport Network Theory Unit, London (1967)

19. Ramalingam, G., Reps, T.: An incremental algorithm for a generalization of the shortest path problem. J. Algorithm 21, 267-305(1996)

20. Rodionov, V.: The parametric problem of shortest distances. USSR Comp. Math. Math. Phys. 8(5), 336-343 (1968)

21. Rohnert, H.: A dynamization of the all-pairs least cost problem. In: Proc. 2nd Annual Symposium on Theoretical Aspects of Computer Science, (STACS'85). LNCS, vol. 182, pp. 279-286. Springer, Berlin (1985)

22. Thorup, M.: Fully-dynamic all-pairs shortest paths: Faster and allowing negative cycles. In: Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT'04), pp. 384-396. Springer, Berlin (2004)

23. Thorup, M.: Worst-case update times for fully-dynamic all-pairs shortest paths. In: Proceedings of the 37th ACM Symposium on Theory of Computing (STOC 2005), ACM. New York (2005)

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