4824
правки
Полностью динамический алгоритм нахождения кратчайших путей между всеми парами: различия между версиями
Перейти к навигации
Перейти к поиску
Полностью динамический алгоритм нахождения кратчайших путей между всеми парами (посмотреть исходный код)
Версия от 06:24, 25 мая 2014
, 25 мая 2014→Постановка задачи
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
Динамический алгоритм на графе поддерживает заданное свойство P графа, подверженного динамическим изменениям – таким как вставка дуги, удаление дуги и обновление веса дуги. Динамический алгоритм должен быстро обрабатывать запросы о свойстве P, а также выполнять операции обновления быстрее, чем вычислять то же самое с нуля при помощи самого быстрого статического алгоритма. Алгоритм называется полностью динамическим, если он поддерживает как вставку дуг, так и удаление дуг. Частично динамический алгоритм поддерживает либо вставку, либо удаление дуг; инкрементный алгоритм поддерживает только вставку дуг, декрементный – только удаление. В данном случае рассматриваются полностью динамические алгоритмы вычисления кратчайших путей в ориентированных графах общего вида. | Динамический алгоритм на графе поддерживает заданное свойство P графа, подверженного динамическим изменениям – таким как вставка дуги, удаление дуги и обновление веса дуги. Динамический алгоритм должен быстро обрабатывать запросы о свойстве P, а также выполнять операции обновления быстрее, чем вычислять то же самое с нуля при помощи самого быстрого статического алгоритма. Алгоритм называется [[полностью динамический алгоритм|полностью динамическим]], если он поддерживает как вставку дуг, так и удаление дуг. [[Частично динамический алгоритм]] поддерживает либо вставку, либо удаление дуг; [[инкрементный алгоритм]] поддерживает только вставку дуг, [[декрементный алгоритм|декрементный]] – только удаление. В данном случае рассматриваются полностью динамические алгоритмы вычисления кратчайших путей в ориентированных графах общего вида. | ||
| Строка 20: | Строка 20: | ||
Пусть n и m обозначают число вершин и дуг графа G, соответственно. | Пусть n и m обозначают число вершин и дуг графа G, соответственно. | ||
Деметреску и Итальяно [3] предложили новый подход к решению динамических задач нахождения путей, основанный на поддержке классов путей, характеризующихся локальными свойствами – то есть свойствами, выполняющимися для всех подходящих подпутей, даже если они не обязательно выполняются для целых путей. Авторы показали, что этот подход может сыграть важнейшую роль в процессе динамической поддержки кратчайших путей. | Деметреску и Итальяно [3] предложили новый подход к решению динамических задач нахождения путей, основанный на поддержке классов путей, характеризующихся локальными свойствами – то есть свойствами, выполняющимися для всех подходящих подпутей, даже если они не обязательно выполняются для целых путей. Авторы показали, что этот подход может сыграть важнейшую роль в процессе динамической поддержки кратчайших путей. | ||
== Основные результаты == | == Основные результаты == | ||