Вот и наступило лето. Точнее оно наступило 25 дней назад, но ощутил я его только сегодня, потому что я приехал на дачу.
Этот день начинался так, как начинаются все летние деньки, ничем не отличающиеся от остальных дней. Проснулся я, как и полагается, где-то днём, не помню уже точно во сколько. Проснувшись, я решил найти что-нибудь перекусить, но в холодильнике ничего не было. Только висела записка: "Продукты в магазине. Будем поздно. Не скучай".
Понятно, чтобы не умереть с голоду, надо было идти в магазин. Но идти пешком я туда, конечно, не собирался. Велосипед мне на что?) Я быстро нашёл его в гараже и поехал в магазин. Ехал я просто прямо, так как заасфальтированная дорога была только одна, а по песку я как-то не хотел кататься. Я думал, что ничто не сможет испортить мне поездку в магазин. Наивный... На повороте я остановился, точнее меня остановил какой-то дядя, сказав, что придётся объезжать. Разумеется, у меня возник вопрос: "Откуда в деревне нашлись деньги на ремонт дороги, и зачем её вообще было ремонтировать, когда она была в довольно неплохом состоянии?". Лично я знаю места, где дорога выглядит намного хуже. Но ничего не поделаешь, надо было разворачиваться. Теперь, когда ехать пришлось по песку, я включил информатика в своей голове и быстро нашёл кратчайший путь до магазина и обратно.
Приехав домой, я первым делом поел. Кушая, я всё думал об этом ремонте дороги. Грубо говоря, они удалили одно ребро из графа, а я добавил новую вершину в него, когда меня отправили в объезд. И я начал думать над более общей задачей.
Пусть наша программа должна уметь обрабатывать следующие запросы:
Добавить новую вершину в граф.
Удалить вершину из графа.
Добавить новое ребро.
Удалять ребро из графа.
Для пары вершин посчитать кратчайшее расстояние между ними.
Разумеется, что рёбра имеет свой вес. Допускается наличие кратных рёбер, хотя можно и без них. И количество вершин N<=10^5,а рёбер M<=10^5. Все запросы нужно обрабатывать online.
Вот с такой задачей в голове я пошёл загорать на пляж. Вернувшись с речки, я так и не придумал решение данной задачи. Может у кого-нибудь есть идеи, как решать её? Или идеи, как обрабатывать может не все запросы, а только некоторые из них? Пятый запрос нужно обрабатывать всегда.
А Вы умеете отвечать хотя бы на один пятый запрос лучше, чем за сложность Дейкстры?
P.S. Под "одним пятым запросом" я имел в виду то, что у нас будет дан фиксированный граф, и нам нужно будет отвечать только на запросы пятого типа.
Ну, очевидно если в фиксированном графе M ребер а количество запросов Q >> M то сложность амортизированная будет гораздо меньше :)
Разве автор не об этом и спрашивает — существует ли способ так накапливать инфу по мере запросов и изменений в графе, что сложность в среднем станет меньше чем для одного запроса в неизвестном заранее графе. %)
Сорри если я что-то недопонял...
UPD: вроде можно представить некий громоздкий способ который будет обрабатывать только запросы 2, 4 и 5 — хранить для пар вершин текущие пути, смотреть какие пути аффектит очередное удаление и т.п. Правда непохоже чтобы это давало экономию для произвольного запроса. Удобнее всего если обнаруживается что удалено ребро не входящее ни в какие пути. При добавлении ребра... Хм... Мы пересчитаем пути для вершин которых ребро касается, а потом для тех вершин расстояние до которых изменилось и так далее... Я не в силах оценить достаточно ли будет этого %)
В общем похоже жиденькая экономия :D
Ну, очевидно, можно при каждом запуске Дейкстры сохранять длины кратчайших путей из исходных вершин — получим почти что алгоритм Джонсона за O(N * M * log N), только без потенциалов. Вся соль задачи в том, что в авторских ограничениях она СП-шными методами как бы и не решается :).
Комментарий к UPD: да, на практике я и сам бы начал пихать подобные эвристики (очевидно, что асимптотику худшего случая они не улучшают, но на реальных данных все бы работало весьма быстро).
Да... Согласен. Просто я авторских ограничений на время не видел — но если руководствоваться типичными 1-2 секунды... Гм. :)
Автор поста явно пытается изобрести автомобильный навигатор, но с расчётом путей на центральном сервере вместо того чтобы каждый на своём девайсе решал это дело... :D
Вообще, на самом деле, Jokser когда-то придумал задачу, схожую с Вашей по сути (даже проще). Оригинал: дан произвольный граф, нужно выкинуть из него ребро так, чтобы расстояние между заданными вершинами A и B стало максимально возможным. Я сделал очевидное сведение к онлайн задаче о поддержании кратчайшего пути между А и В с возможностью добавления ребер, но даже это нам решить за время лучше O(N) на добавление ребра не удалось.
Очевидно что задачу с данными Вами ограничениями решить нельзя. Давайте рассмотрим только запросы третьего типа. При добавлении нового ребра из каждой вершины может найтись путь(хотя бы один), который пройдет через данное ребро. А может его и не найтись. И никакой функции, по которой мы могли бы определить заранее, для каких вершин нам нужно вычислять, может ли какой-то из путей использовать новое добавленное ребро, а из каких — нет, не существует. Следовательно, нужно проверять каждую вершину. Следовательно, асимптотика на добавление не может быть меньше O(N).
Прежде, чем ставить нерешаемые задачи перед сообществом, решите хотя бы более простые. Лично я не знаю как поставленную Вами задачу решать даже для N < 10^4, M < 10^4(если предположить что асимптотику N*M*logN не получится протолкнуть, нужно решать за чистый N*M). Вы хотя бы такую задачу решать умеете?
ОК, я знаю, как решать задачу за O(N * M * log log D), где D — максимальное расстояние между вершинами.
Ключ к решению под спойлером.
спойлер
Спойлер
Как раз недавно смотрел лекцию по этой теме:) Поправьте если не прав.