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

В современной литературе предлагаются две основные идеи о том, как преобразовать эту ситуацию в задачу о кратчайшем пути на графе. В качестве примера рассмотрим упрощенную модель, в которой пересадка не занимает времени, в запросах указывается время начала поездки и станция, а результатом запроса должен быть маршрут с самым ранним временем прибытия в пункт назначения.

В модели, растянутой по времени [ ], каждое событие прибытия и отправления в расписании является вершиной ориентированного графа. Дуги графа представляют собой последовательные события на одной станции и прямые согласования поездов. Длина дуги задается разницей во времени между ее конечными вершинами. Пусть s – вершина на станции отправления, время которой непосредственно следует за начальным временем. Кратчайший путь от s до любой вершины станции назначения является оптимальным маршрутом.

В модели, зависящей от времени [3, 7, 9, 10], вершины моделируют станции, а дуги означают наличие прямого (безостановочного) железнодорожного сообщения. Вместо длины ребра, дуги помечаются функциями обхода ребра, которые сообщают время прибытия в конечную точку дуги в зависимости от времени начала движения пассажира в начале дуги, отражая время, фактически проходимое поездом. Для решения этой зависящей от времени задачи о кратчайшем пути можно использовать модификацию алгоритма Дейкстры. Используя структуру этой ситуации, можно выбрать такое представление графа, которое позволяет оценивать функции обхода звеньев за константное время [ ]. Для обработки более реалистичных моделей пересадок можно использовать более сложный граф.