Маршрут перелётов
Условие
fetchFlights(from) возвращает массив городов, куда есть прямой рейс. Найди маршрут из from в to как массив городов, включая обе точки. Если маршрута нет - строка 'Нет маршрута'. Маршрут должен быть с минимальным числом пересадок.
Что проверяют тесты
прямой маршрут
через пересадки
старт равен финишу
маршрута нет
кратчайший из нескольких
цикл не зацикливает
Как подойти
BFS гарантирует минимальное число пересадок, DFS - нет. Хранение путей целиком в очереди проще, чем карта предшественников, и на размерах реальных маршрутных сетей приемлемо. Пометка посещённых при добавлении в очередь, а не при извлечении, не даёт очереди раздуться. Отсутствующий город в справочнике возвращает undefined - оператор || закрывает это.
Подсказки: 3
- Кратчайший путь по числу рёбер - это обход в ширину.
- В очереди удобно держать целые пути, а не только вершины.
- Город без рейсов даёт undefined - подстрахуйся.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.