Как найти самый длинный путь в графе с набором начальных и целевых точек?

Question

У меня есть DAG (с затратами/весами на край) и хотите найти самый длинный путь между двумя наборами узлов. Два набора начальных и целевых узлов являются непересекающимися и малыми по сравнению с общим числом узлов на графике.

Я знаю, как это сделать эффективно между один стартовый и целевой узел. С несколькими я могу перечислить все пути от каждого запуска до каждого целевого узла и выбрать самый длинный, но это займет квадратное число поисков одиночного пути. Есть ли способ лучше?

Answer 1

Я предполагаю, что вам нужен самый длинный путь, который запускается в любом из узлов из первого набора и заканчивается в любом из узлов второго набора. После этого вы можете добавить два виртуальные узлы:

• Первый узел не имеют предшественников и его преемники являются узлами из первого набора.

• Второй узел не имеет преемников, а его предшественниками являются узлы второго набора.

Все вновь добавленные края должны иметь нулевой вес.

График все еще будет DAG. Теперь, если вы используете стандартный алгоритм для поиска самого длинного пути в DAG между двумя новыми узлами, вы получите самый длинный путь, который начинается в первом наборе и заканчивается во втором наборе, за исключением того, что будет добавлен дополнительный нуль- взвешенный край в начале и дополнительный нулевой вес в конце.

Кстати, это решение, по сути, выполняет алгоритм из всех узлов из первого набора, но параллельно, в отличие от последовательного подхода, который предлагает ваш вопрос.