4817
правок
Декрементный алгоритм нахождения кратчайших путей между всеми парами: различия между версиями
Перейти к навигации
Перейти к поиску
Декрементный алгоритм нахождения кратчайших путей между всеми парами (посмотреть исходный код)
Версия от 15:39, 20 апреля 2013
, 20 апреля 2013→История задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 16: | Строка 16: | ||
== История задачи == | == История задачи == | ||
Простое решение этой задачи заключается в реконструкции кратчайших путей с нуля после каждого удаления при помощи лучшего статического APSP-алгоритма, что позволит выполнять запросы о расстоянии и пути за оптимальное время. Лучший из известных статических APSP-алгоритмов для графа с произвольными действительными весами дуг выполняется за время O(mn + | Простое решение этой задачи заключается в реконструкции кратчайших путей с нуля после каждого удаления при помощи лучшего статического 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) в худшем случае, тогда как обновления выполняются за оптимальное время. | Еще одним простым решением является ответ на запросы путем поточечного вычисления кратчайших путей, без необходимости обновления кратчайших путей после каждого удаления дуги. Это можно выполнить при помощи алгоритма Дейкстры [ ] за время O(m + n log n), используя фибоначчиевы кучи из метода Фредмана-Тарьяна [ ]. Подобный подход позволяет давать ответы на запросы за время O(m + n log n) в худшем случае, тогда как обновления выполняются за оптимальное время. | ||
| Строка 23: | Строка 23: | ||
Первый декрементный алгоритм с предположительно меньшим временем работы по сравнению с перевычислением с нуля предложила Валери Кинг для специального случая графов с целочисленными весами дуг величиной не более C; ее алгоритм способен обновлять кратчайшие пути в графе после серии из Q{n2) удалений, где каждое удаление производится за амортизированное время O(C ■ n2) [ ]. Позднее Деметреску и Италиано показали, как обрабатывать графы с действительными неотрицательными весами дуг за амортизированное время O(n2 log n) на одно удаление [2] в последовательности из Q{mln) операций. Оба алгоритма работают и в более общем случае, когда дуги не удаляются из графа, но их вес увеличивается с каждым обновлением. Более того, поскольку эти алгоритмы явно обновляют кратчайшие пути после каждого удаления, ответы на запросы выдаются за оптимальное время в любой момент последовательности операций. | Первый декрементный алгоритм с предположительно меньшим временем работы по сравнению с перевычислением с нуля предложила Валери Кинг для специального случая графов с целочисленными весами дуг величиной не более C; ее алгоритм способен обновлять кратчайшие пути в графе после серии из Q{n2) удалений, где каждое удаление производится за амортизированное время O(C ■ n2) [ ]. Позднее Деметреску и Италиано показали, как обрабатывать графы с действительными неотрицательными весами дуг за амортизированное время O(n2 log n) на одно удаление [2] в последовательности из Q{mln) операций. Оба алгоритма работают и в более общем случае, когда дуги не удаляются из графа, но их вес увеличивается с каждым обновлением. Более того, поскольку эти алгоритмы явно обновляют кратчайшие пути после каждого удаления, ответы на запросы выдаются за оптимальное время в любой момент последовательности операций. | ||
== Основные результаты == | == Основные результаты == | ||