Декрементный алгоритм нахождения кратчайших путей между всеми парами: различия между версиями

Декрементный APSP-алгоритм, разработанный Деметреску и Италиано, основывается на понятии локально кратчайших путей [2]. Путь является локально кратчайшим в графе, если все его собственные подпути являются кратчайшими путями.

Согласно свойству оптимальности подструктуры, кратчайший путь является локально кратчайшим. Основная идея алгоритма заключается в том, чтобы хранить информацию о локально кратчайших путях в графе, в котором планируется удаление дуг. Теорема 1, приведенная в [], ограничивает число изменений в множестве локально кратчайших путей, связанных с удалением дуг.

Теорема 1. Если кратчайшие пути являются уникальными в графе, то количество путей, которые становятся кратчайшими или перестают быть кратчайшими после каждого удаления дуги, равно O(n2) в результате амортизации по Q{mln) операциям обновления.

Результат теоремы 1 является чисто комбинаторным; он предполагает, что кратчайшие пути уникальны в графе. Последнее можно легко установить при помощи любой согласованной стратегии разрешения спорных ситуаций (см., например, [ ]). Можно разработать алгоритм, включающий только удаления, который будет тратить только O(log n) времени на одно изменение в множестве локально кратчайших путей, используя простую модификацию алгоритма Дейкстры []. Поскольку, согласно теореме 1, амортизированное число изменений ограничено O(n2), из этого следует:

Теорема 2. Рассмотрим граф, содержащий n вершин и изначально m дуг, в котором последовательно производится Q(mln) удалений дуг. Если кратчайшие пути являются уникальными, а веса дуг – неотрицательными, то каждую операцию удаления можно выполнить за амортизированное время O(n2logn), каждый запрос о расстоянии – за время O(1) в худшем случае, а каждый запрос о пути – за время O(1) в худшем случае, где I – число вершин в отмеченном кратчайшем пути. Объем требуемой памяти – O(mn).