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

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


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


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

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

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

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


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

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

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

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


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

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

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

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

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


== Открытые вопросы ==
Недавние исследования в области динамических алгоритмов нахождения кратчайших путей поставили новые и весьма интересные вопросы. Можно ли уменьшить объем памяти, необходимой динамическому алгоритму нахождения кратчайших путей, до <math>O(n^2) \; </math>? Возможно, еще более важный вопрос заключается в том, можно ли эффективно решить полностью динамическую задачу достижимости и нахождения кратчайших путей ''с единственным источником'' на графах общего вида? Наконец, существуют ли техники общего вида, позволяющие сделать полностью динамическими алгоритмы, использующие только приращение? Подобные техники широко использовались в случае полностью динамических алгоритмов на неориентированных графах [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)