найти маршрут от a до b

Question

Я хочу найти маршрут от a до b, используя общественный транспорт. Предположим, что я нашел путь от a до b (например, остановки последовательности от a до b), но как создать маршрут (например, перейти от A к D на шине 3, затем взять автобус 15 из D в B)? Я использую метод глубины, чтобы создать граф, соединяющий остановки по транспорту (учитывая подключение по длине).

Answer 1

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