4817
правок
Декрементный алгоритм нахождения кратчайших путей между всеми парами: различия между версиями
Перейти к навигации
Перейти к поиску
Декрементный алгоритм нахождения кратчайших путей между всеми парами (посмотреть исходный код)
Версия от 15:47, 20 апреля 2013
, 20 апреля 2013→История задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 18: | Строка 18: | ||
Простое решение этой задачи заключается в реконструкции кратчайших путей с нуля после каждого удаления при помощи лучшего статического APSP-алгоритма, что позволит выполнять запросы о расстоянии и пути за оптимальное время. Лучший из известных статических APSP-алгоритмов для графа с произвольными действительными весами дуг выполняется за время <math>O(mn + n^2 log \; log n)</math>, где m – количество дуг, а n – количество вершин графа [13]. В худшем случае это составляет <math>O(n^3) \; </math>. Фредман [6] и позднее Такаока [19] показали, как разрушить кубический барьер; лучшая асимптотическая граница решения APSP-задачи найдена Такаокой и составляет <math>O(n^3 \sqrt{log log n/log n})</math>. | Простое решение этой задачи заключается в реконструкции кратчайших путей с нуля после каждого удаления при помощи лучшего статического APSP-алгоритма, что позволит выполнять запросы о расстоянии и пути за оптимальное время. Лучший из известных статических APSP-алгоритмов для графа с произвольными действительными весами дуг выполняется за время <math>O(mn + n^2 log \; log n)</math>, где m – количество дуг, а n – количество вершин графа [13]. В худшем случае это составляет <math>O(n^3) \; </math>. Фредман [6] и позднее Такаока [19] показали, как разрушить кубический барьер; лучшая асимптотическая граница решения APSP-задачи найдена Такаокой и составляет <math>O(n^3 \sqrt{log log n/log n})</math>. | ||
Еще одним простым решением является ответ на запросы путем поточечного вычисления кратчайших путей, без необходимости обновления кратчайших путей после каждого удаления дуги. Это можно выполнить при помощи алгоритма Дейкстры [ ] за время O(m + n log n), используя фибоначчиевы кучи из метода Фредмана-Тарьяна [ ]. Подобный подход позволяет давать ответы на запросы за время O(m + n log n) в худшем случае, тогда как обновления выполняются за оптимальное время. | Еще одним простым решением является ответ на запросы путем поточечного вычисления кратчайших путей, без необходимости обновления кратчайших путей после каждого удаления дуги. Это можно выполнить при помощи алгоритма Дейкстры [3] за время <math>O(m + n \; log n) \; </math>, используя фибоначчиевы кучи из метода Фредмана-Тарьяна [5]. Подобный подход позволяет давать ответы на запросы за время <math>O(m + n \; log n) \; </math> в худшем случае, тогда как обновления выполняются за оптимальное время. | ||
Динамические алгоритмы вычисления кратчайших путей разрабатывались уже давно; первые статьи по этой теме датированы 1967 годом [11,12,17]. В 1985 Ивэн и Гацит [ ] представили алгоритмы вычисления кратчайших путей в ориентированных графах с произвольными действительными весами. Время работы алгоритма для удаления дуг в худшем случае сравнимо с вычислением APSP с нуля. Рамалингам и Репс [15, 16], а также Фригиони и коллеги [7, 8] рассматривали динамические алгоритмы вычисления кратчайших путей для графа с действительными весами на базе другой модели; время исполнения алгоритма рассматривалось с точки зрения изменения выходного графа, а не в терминах размера входного графа (сложность в виде выходного ограничения). Время работы динамических алгоритмов с выходным ограничением в худшем случае также сравнимо с вычислением APSP с нуля. | Динамические алгоритмы вычисления кратчайших путей разрабатывались уже давно; первые статьи по этой теме датированы 1967 годом [11, 12, 17]. В 1985 Ивэн и Гацит [4] представили алгоритмы вычисления кратчайших путей в ориентированных графах с произвольными действительными весами. Время работы алгоритма для удаления дуг в худшем случае сравнимо с вычислением APSP с нуля. Рамалингам и Репс [15, 16], а также Фригиони и коллеги [7, 8] рассматривали динамические алгоритмы вычисления кратчайших путей для графа с действительными весами на базе другой модели; время исполнения алгоритма рассматривалось с точки зрения изменения выходного графа, а не в терминах размера входного графа (сложность в виде выходного ограничения). Время работы динамических алгоритмов с выходным ограничением в худшем случае также сравнимо с вычислением APSP с нуля. | ||
Первый декрементный алгоритм с предположительно меньшим временем работы по сравнению с перевычислением с нуля предложила Валери Кинг для специального случая графов с целочисленными весами дуг величиной не более C; ее алгоритм способен обновлять кратчайшие пути в графе после серии из | Первый декрементный алгоритм с предположительно меньшим временем работы по сравнению с перевычислением с нуля предложила Валери Кинг для специального случая графов с целочисленными весами дуг величиной не более C; ее алгоритм способен обновлять кратчайшие пути в графе после серии из <math>\Omega (n^2) \; </math> удалений, где каждое удаление производится за амортизированное время <math>O(C \cdot n^2 \; )</math> [9]. Позднее Деметреску и Италиано показали, как обрабатывать графы с действительными неотрицательными весами дуг за амортизированное время <math>O(n^2 \; log n) \; </math> на одно удаление [2] в последовательности из <math>\Omega (m/n) \; </math> операций. Оба алгоритма работают и в более общем случае, когда дуги не удаляются из графа, но их вес увеличивается с каждым обновлением. Более того, поскольку эти алгоритмы явно обновляют кратчайшие пути после каждого удаления, ответы на запросы выдаются за оптимальное время в любой момент последовательности операций. | ||
== Основные результаты == | == Основные результаты == | ||