Comments 11
А в демо-базе все равно только самолеты.
и что если вместо
Представление «пути» в виде массива помогает во многих случаях
использовать для этой цели тип данных ltree.
может это жесткач будет но что если зная что у нас не может быть level больше 6, предварительно сделать таблицу(матвьюху) со всеми вариантами полученных «путей» для каждого узла в формате ltree + gin индекс на это поле
и тогда все запросы сведутся к поиску веток по индексу, а выше разобранный запрос использовать для заполнения ltree-)
Честно говоря, не уверен, что план запроса в этом случае чем-то поможет, поэтому не стал загромождать и без того довольно длинную заметку. Но все это можно легко повторить самостоятельно и посмотреть любые планы.
Насчет ltree + gin gist — почему бы и нет, если перелеты статические, а искать надо часто. И к тому же как-нибудь хитро, типа «из A в B через C», потому что иначе достаточно обычного индекса.
Какое максимальное число пересадок потребуется, чтобы добраться из любого аэропорта в любой другой?
Точно не минимальное? Нужно найти все варианты пути без циклов и выбрать из них самый длинный и так для каждой пары аэропортов?
Если говорить формально, то так: найти минимальное число N такое, что из произвольного аэропорта A можно добраться в произвольный аэропорт B, используя меньшее либо равное N число пересадок.
То есть нас интересует число пересадок, которое потребуется в худшем случае. Поэтому надо найти кротчайшие пути для всех пар аэропортов и выбрать из них максимальный.
И снова о рекурсивных запросах