Определение пути перелёта между двумя пунктами

Условие

Реализуйте функцию, получающую начальную и конечную точку и асинхронный метод fetchFlights, который возвращает список доступных направлений из указанного города. Функция должна вернуть Promise.resolve с массивом пунктов, образующих маршрут, либо Promise.reject с ошибкой, содержащей текст "No way".

// метод, возвращающий список прямых рейсов из города
function fetchFlights(from: string): Promise<string[]>;

// Пример графа маршрутов: {A: [B, D], B: [C, N, Z], D: [E, F], F: [S]}

findPath('A', 'N', fetchFlights) // Promise.resolve(['A', 'B', 'N'])
findPath('A', 'S', fetchFlights) // Promise.resolve(['A', 'D', 'F', 'S'])
findPath('B', 'S', fetchFlights) // Promise.reject(new Error('No way'))

// реализация функции поиска составного авиаперелёта
function findPath(start, end, fetchFlights) {
    // ваш код здесь
}

Ответ

Выполните асинхронный поиск в ширину, сохраняя предшественников и посещённые города. Он найдёт маршрут с минимумом перелётов; при отсутствии пути выбросьте Error('No way').

async function findPath(start, end, fetchFlights) {
  if (start === end) return [start];
  const parent = new Map([[start, null]]);
  const queue = [start];
  for (let head = 0; head < queue.length; head++) {
    const city = queue[head];
    for (const next of await fetchFlights(city)) {
      if (parent.has(next)) continue;
      parent.set(next, city);
      if (next === end) {
        const path = [end];
        let current = end;
        while (current !== start) {
          current = parent.get(current);
          path.push(current);
        }
        return path.reverse();
      }
      queue.push(next);
    }
  }
  throw new Error('No way');
}

Циклы не вызывают бесконечный обход: каждый город запрашивается не более одного раза. Ошибка загрузки рейсов передаётся вызывающему коду, а не маскируется отсутствием маршрута. Для конечного графа время обхода O(V + E) без учёта сетевых задержек, память O(V).