На базе вы будете рассматривать свою городскую сеть в виде дерева, в котором вылетающий город является корневым, а каждый вылетающий рейс - указателем на ребенка. Вы будете выполнять рекурсивный поиск в глубине по дереву, чтобы найти все пути к месту назначения, но при этом проверяете цикл по ходу и прерываете любой путь, который приводит к циклу.
По мере того как вы находите возможные пути, вы можете либо просто оставить кратчайшее, но найденное единственное решение; или оставьте большее подмножество найденных путей, рассортированных по некоторым критериям во времени отправления, если вы хотите выбрать на этой основе.
В зависимости от специфики базы данных и узлов, вы также можете добавить другие правила для сокращения ваших путей поиска, например, если вы знаете, что отправление и пункт назначения находятся на расстоянии 1000 миль, и ваш путь, который отслеживается до сих пор ты пролетел 3000 миль, а тебя все еще нет, прикрути его, иди к следующему поиску пути.