Полностью динамический алгоритм нахождения кратчайших путей между всеми парами
Постановка задачи
Задача заключается в эффективной поддержке информации о кратчайших путях между всеми парами в динамически меняющемся графе. Эта задача исследовалась еще с 60-х годов [17, 18, 20]; она играет важнейшую роль во множестве приложений, включая такие области, как оптимизация и маршрутизация сетей, системы управления информацией о дорожном движении, базы данных, компиляторы, сбор мусора, интерактивные системы верификации, робототехника, анализ потоков данных и форматирование документов.
Динамический алгоритм на графе поддерживает заданное свойство P графа, подверженного динамическим изменениям – таким как вставка дуги, удаление дуги и обновление веса дуги. Динамический алгоритм должен быстро обрабатывать запросы о свойстве P, а также выполнять операции обновления быстрее, чем вычислять то же самое с нуля при помощи самого быстрого статического алгоритма. Алгоритм называется полностью динамическим, если он поддерживает как вставку дуг, так и удаление дуг. Частично динамический алгоритм поддерживает либо вставку, либо удаление дуг; инкрементный алгоритм поддерживает только вставку дуг, декрементный – только удаление. В данном случае рассматриваются полностью динамические алгоритмы вычисления кратчайших путей в ориентированных графах общего вида.
В задаче нахождения кратчайших путей между всеми парами (APSP) необходимо поддерживать ориентированный граф G = (V, E) с дугами, имеющими вещественные веса, и выполнение последовательности следующих операций в различном порядке:
Update(x, y, w): обновление веса дуги (x, y) с присвоением вещественного значения w; эта операция включает в качестве специальных случаев вставку дуги (если вес меняется с +1 на w < +1) и удаление дуги (если вес устанавливается равным w = +1);
Distance(x, y): возвращает кратчайшее расстояние от x до y.
Path(x, y): возвращает кратчайший путь между x и y, если таковой существует.
Более формально эту задачу можно определить следующим образом.
Задача 1 (Полностью динамический алгоритм нахождения кратчайших путей между всеми парами)
Дано: взвешенный ориентированный граф G = (V, E) и вышеописанная последовательность операций.
Требуется: найти матрицу D, такую, что ячейка матрицы D[x, y] хранит расстояние между вершинами x и y на протяжении всей последовательности операций.
Пусть n и m обозначают число вершин и дуг графа G, соответственно.
Деметреску и Итальяно [3] предложили новый подход к решению динамических задач нахождения путей, основанный на поддержке классов путей, характеризующихся локальными свойствами – то есть свойствами, выполняющимися для всех подходящих подпутей, даже если они не обязательно выполняются для целых путей. Авторы показали, что этот подход может сыграть важнейшую роль в процессе динамической поддержки кратчайших путей.
Основные результаты
Теорема 1. Полностью динамическая задача нахождения кратчайших путей может быть решена за амортизированное время O(n2 log3 n) на одно обновление при помощи выполнения любой последовательности операций. Объем требуемой памяти составляет O(mn). Используя тот же подход, Торуп [22] показал, как можно несколько улучшить время исполнения: Теорема 2. Полностью динамическая задача нахождения кратчайших путей может быть решена за амортизированное время in O(n2(log n + log2(m/n))) на одно обновление при помощи выполнения любой последовательности операций. Объем требуемой памяти составляет 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)