Поиск пути между аэропортами с применением обхода в глубину

Условие

Необходимо реализовать функцию, которая определит любую возможную последовательность перелётов от исходного аэропорта до конечного. Функция принимает три аргумента: код аэропорта отправления, код аэропорта назначения и функцию‑поставщик билетов. Результатом работы функции должен быть Promise, который либо разрешается массивом всех промежуточных пунктов (например, ['A','B','C']), либо строкой "no way", если путь недоступен.

Гарантируется, что для заданных пунктов существует либо один единственный маршрут, либо вовсе нет (нет ситуаций с несколькими альтернативными ветвями). При поиске нельзя запускать несколько запросов одновременно, а также запрещено использовать синтаксис async/await и генераторы.

const flights = [
  ['A', 'B'],
  ['A', 'С'],
  ['A', 'D'],
  ['A', 'O'],
  ['D', 'K'],
  ['D', 'L'],
  ['D', 'M'],
  ['M', 'Q'],
  ['M', 'Z'],
  ['O', 'P'],
  ['L', 'G'],
  ['L', 'F'],
  ['F', 'Y'],
];

findPath('A', 'N', fetchFlighting).then(console.log) // Promise.resolve(['A', 'D', 'N'])
findPath('A', 'Q', fetchFlighting).then(console.log) // Promise.resolve(["A", "D", "M", "Q"])
findPath('A', 'W', fetchFlighting).then(console.log) // 'no way'

Ответ

Свяжите шаги DFS через then, запрашивая соседей одного аэропорта за раз. В показанном графе маршрута A → N нет: пример ['A','D','N'] противоречит списку рейсов.

Ниже предполагается контракт fetchFlighting(city) → Promise<string[]> со списком прямых направлений.

function findPath(start, end, fetchFlighting) {
  const seen = new Set();
  function visit(city, path) {
    if (city === end) return Promise.resolve(path);
    if (seen.has(city)) return Promise.resolve(null);
    seen.add(city);
    return Promise.resolve().then(() => fetchFlighting(city)).then(next => {
      let index = 0;
      function searchNext() {
        if (index === next.length) return Promise.resolve(null);
        const target = next[index++];
        return visit(target, [...path, target]).then(result => result ?? searchNext());
      }
      return searchNext();
    });
  }
  return visit(start, [start]).then(path => path ?? 'no way');
}

Нет async/await, генераторов и параллельных запросов. seen защищает от циклов; цепочка Promise продолжает поиск лишь после завершения ветки. Сетевая ошибка отклоняет Promise и не маскируется строкой no way.