У меня есть DAG (с затратами/весами на край) и вы хотите найти самый длинный путь между двумя наборами узлов. Два набора начальных и целевых узлов являются непересекающимися и малыми по сравнению с общим числом узлов на графике.
Я знаю, как это сделать эффективно между одним стартом и целью node. С несколькими я могу перечислить все пути от каждого старта до каждой цели node и выбрать самый длинный, но это займет квадратное число поисков одиночного пути. Есть ли лучший способ?
Я предполагаю, что вам нужен самый длинный путь, который запускается в любом из узлов из первого набора и заканчивается в любом из узлов во втором наборе. Затем вы можете добавить два виртуальных узла:
Первый node не имеет предшественников, а его преемниками являются узлы из первого набора.
Второй node не имеет преемников, а его предшественниками являются узлы из второго набора.
Все вновь добавленные края должны иметь нулевой вес.
График все равно будет DAG. Теперь, если вы используете стандартный алгоритм для поиска самого длинного пути в DAG между двумя новыми узлами, вы получите самый длинный путь, который начинается в первом наборе и заканчивается во втором наборе, за исключением того, что будет добавлен дополнительный нулевой вес в начале и дополнительный нулевой вес в конце.
Кстати, это решение по существу выполняет алгоритм из всех узлов из первого набора, но параллельно, в отличие от последовательного подхода, который предлагает ваш вопрос.