Как найти кратчайший путь в динамическом графе?

Задача не самая тривиальная, но и не самая сложная: найти кратчайший путь между двумя точками графа.
Проблема заключается в том, что в зависимости от времени (суммы пройденной по ребрам) расположение ребер может поменяться.

Т.е. мне нужно найти маршрут из точки A в точку B с пересадками, при этом учитывая, что в разное время ездят разные маршруты (некоторые раз в день, некоторые 2-3 раза в день, то есть не так уж часто).

Возможно такое можно провернуть со стандартными алгоритмами, но не могу приложить ума как. Может есть хоть какие-то идеи, в каком направлении копать, какие алгоритмы изучить еще тщательнее, чтобы найти лазейку.
  • Вопрос задан
  • 4285 просмотров
Пригласить эксперта
Ответы на вопрос 5
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
IMHO, у Вас не совсем корректная модель. Сами рёбра графа никуда не исчезают, меняется их цена. То есть, если из A в B мы можем попасть в момент T, то цена ребра B-C будет равняться времени от момента T до момента самого раннего прибытия маршрута из B в C с учётом отправления не ранее T+время на пересадку.
Ответ написан
@luckman
Если можно останавливаться в точках на какое угодно время, то вроде должен подойти обычный алгоритм Дейкстры.
Если нет, то динамика f[t, p] - можно ли оказаться в точке p в момент времени t

Может есть и получше варианты, но это первое, что пришло в голову
Ответ написан
Комментировать
@Exact Автор вопроса
На какое угодно - нельзя в этом и проблема.
"динамика f[t, p]", а где про это можно почитать, чет я инфы не нашел об этом, как в алгоритм встроить динамику или как просто её использовать.
Или подразумевается непосредственно расчет и определение значения данной функции для каждой точки маршрута?
Ответ написан
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Утверждение: Рассмотрим какую-то вершину v. Допустим самый ранний момент, в который можно попасть в нее - t. Если эта вершина есть в кратчайшем пути из вершины a в вершину b, то обязательно есть путь, не длинее, в котором вершина v посещается как раз в момент t.
Такой путь можно получить конструктивно - начало взять из кратчайшего пути в v, а конец из кратчайшего пути из a в b, может придется подождать какое-то время в вершине, прежде чем продолжить путь.

С учетом этого утверждения становится понятно, что можно решать вашу задачу стандартным алгоритмом дейкстры для поиска самого быстрого пути во все вершины. Там при релаксации (пересчете минимального растояния) надо просто учитывать, в какое ближайшее к текущему веремни ребро станет доступно для прохождения.
Ответ написан
Комментировать
@Mamulov
Насколько я понимаю, при динамических весах необходимо в порядке возрастания ребер перебрать все возможные пути, рассчитывая вес каждого ребра с учетом времени, потому, как более всегда малорёберный путь может оказаться длиннее по времени. Можно построить граф, взяв за вес минимальное теоретические время между остановками (у самого быстрого автобуса), а затем отфильтровать заведомо долгие маршруты. Например, был найден маршрут из 5 остановок в 3 часа, который реально (с ожиданием, пересадками и т.п.) займёт 5 часов, значит ищем дальше пока теоретические время графа не превышает 5 часов.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы