Алгоритм: поиск сообщений между городами с ограничением на пересадку поездов
Какой алгоритм вы бы использовали для создания приложения, которое с учетом соответствующих данных (список городов, железнодорожных маршрутов, железнодорожных станций) способно вернуть список соединений между любыми двумя городами, выбранными пользователем? Приложение должно выбирать только те соединения, которые попадают в лимит допустимых пересадок.
Пример:Я спрашиваю у приложения, на каком поезде ехать, если мне нужно ехать из Парижа в Москву с макс. 1 остановка/переключение - приложение возвращает маршрут: Поезд 1 (Париж-Берлин) -> Поезд 2 (Берлин->Москва) (прямого сообщения нет).
Графический пример
Если я запрошу систему о возможных соединениях из города Aв города GЯ получаю ответ:
- Коричневая линия (0 переключений = прямой)
- Коричневая линия до города B / Оранжевая линия до города G (1 переключатель)
- Коричневая линия до города B / Оранжевая линия до города D / Красная Линия до G (2-й переключатель)
- ... все остальные возможности
И хотя 2-й и 3-й варианты короче, чем 1-й, именно 1-й должен иметь приоритет (поскольку переключение поездов не происходит).