Задача не самая тривиальная, но и не самая сложная: найти кратчайший путь между двумя точками графа.
Проблема заключается в том, что в зависимости от времени (суммы пройденной по ребрам) расположение ребер может поменяться.
Т.е. мне нужно найти маршрут из точки A в точку B с пересадками, при этом учитывая, что в разное время ездят разные маршруты (некоторые раз в день, некоторые 2-3 раза в день, то есть не так уж часто).
Возможно такое можно провернуть со стандартными алгоритмами, но не могу приложить ума как. Может есть хоть какие-то идеи, в каком направлении копать, какие алгоритмы изучить еще тщательнее, чтобы найти лазейку.
UPD: Под динамическим графом я подразумеваю граф, в котором грани изменяются в зависимости от прохождения по графу.
Расписание и частота постоянны (в определенном промежутке времени), но в разное время доступны разные рейсы. И если сейчас есть путь B-C-D, то когда мы попадем в точку B из точки A этого пути уже может не быть
Для правильного вопроса надо знать половину ответа
IMHO, у Вас не совсем корректная модель. Сами рёбра графа никуда не исчезают, меняется их цена. То есть, если из A в B мы можем попасть в момент T, то цена ребра B-C будет равняться времени от момента T до момента самого раннего прибытия маршрута из B в C с учётом отправления не ранее T+время на пересадку.
@luckman Если это реальная задача стыковки маршрутов для поездки, то всё равно какое-то допустимое время ожидания придётся заложить. Да и если получится, что самый короткий по времени маршрут предполагает суточное ожидание в транзитном пункте, то маршруте без ожидания придётся все эти сутки провести в транспорте.
А как я смогу узнать, сколько времени понадобится на пересадку, если цену грани заложим изначально? ведь это время будет зависеть оттого, когда мы приедем в эту точку.
В любом случае одним статичным графом на мой взгляд не справиться..
Имеется в виду минимальное время, необходимое чтобы выйти из транспорта/получить багаж/зарегистрироваться на следующий рейс/сесть в следующий транспорт. В реале пересадка вряд ли может быть моментальной.
Рисунок графа будет фиксирован, а вот цена рёбер исходящих из точки будет зависеть от момента прибытия в эту точку.
Если можно останавливаться в точках на какое угодно время, то вроде должен подойти обычный алгоритм Дейкстры.
Если нет, то динамика f[t, p] - можно ли оказаться в точке p в момент времени t
Может есть и получше варианты, но это первое, что пришло в голову
На какое угодно - нельзя в этом и проблема.
"динамика f[t, p]", а где про это можно почитать, чет я инфы не нашел об этом, как в алгоритм встроить динамику или как просто её использовать.
Или подразумевается непосредственно расчет и определение значения данной функции для каждой точки маршрута?
Да, расчёт данной функции в каждой точке p в момент времени t. Время работы будет O(T*P), где P - кол-во точек, T - кол-во единиц времени. Не так быстро, так что нужно посмотреть на ограничения в вашей задаче.
Утверждение: Рассмотрим какую-то вершину v. Допустим самый ранний момент, в который можно попасть в нее - t. Если эта вершина есть в кратчайшем пути из вершины a в вершину b, то обязательно есть путь, не длинее, в котором вершина v посещается как раз в момент t.
Такой путь можно получить конструктивно - начало взять из кратчайшего пути в v, а конец из кратчайшего пути из a в b, может придется подождать какое-то время в вершине, прежде чем продолжить путь.
С учетом этого утверждения становится понятно, что можно решать вашу задачу стандартным алгоритмом дейкстры для поиска самого быстрого пути во все вершины. Там при релаксации (пересчете минимального растояния) надо просто учитывать, в какое ближайшее к текущему веремни ребро станет доступно для прохождения.
Насколько я понимаю, при динамических весах необходимо в порядке возрастания ребер перебрать все возможные пути, рассчитывая вес каждого ребра с учетом времени, потому, как более всегда малорёберный путь может оказаться длиннее по времени. Можно построить граф, взяв за вес минимальное теоретические время между остановками (у самого быстрого автобуса), а затем отфильтровать заведомо долгие маршруты. Например, был найден маршрут из 5 остановок в 3 часа, который реально (с ожиданием, пересадками и т.п.) займёт 5 часов, значит ищем дальше пока теоретические время графа не превышает 5 часов.
