4431
правка
Полностью динамический алгоритм нахождения кратчайших путей между всеми парами: различия между версиями
Перейти к навигации
Перейти к поиску
Полностью динамический алгоритм нахождения кратчайших путей между всеми парами (посмотреть исходный код)
Версия от 13:29, 25 мая 2014
, 25 мая 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 28: | Строка 28: | ||
== Основные результаты == | == Основные результаты == | ||
Теорема 1. Полностью динамическая задача нахождения кратчайших путей может быть решена за амортизированное время O( | '''Теорема 1'''. Полностью динамическая задача нахождения кратчайших путей может быть решена за амортизированное время <math>O(n^2 log^3 n \; )</math> на одно обновление при помощи выполнения любой последовательности операций. Объем требуемой памяти составляет O(mn). | ||
Используя тот же подход, Торуп [22] показал, как можно несколько улучшить время исполнения: | Используя тот же подход, Торуп [22] показал, как можно несколько улучшить время исполнения: | ||
'''Теорема 2'''. Полностью динамическая задача нахождения кратчайших путей может быть решена за амортизированное время <math>O(n^2(log \; n + log^2 (m/n)))</math> на одно обновление при помощи выполнения любой последовательности операций. Объем требуемой памяти составляет O(mn). | |||
== Применение == | == Применение == | ||