Кратчайший путь с обязательным прохождением узлов
Я хочу рассчитать кратчайший путь от источника S к стоку T.
Но путь должен пройти от узла 1, а затем от узла 2, по крайней мере, один раз.
Например: S->...->node1->....->node2->....->T
И мне нужно запускать алгоритм кратчайшего пути только один раз (то есть, мне не разрешается вычислять путь от s до узла1, затем от узла1 до узла2 и, наконец, от узла2 до Т в трех различных вызовах по кратчайшему пути)
Первое, что пришло мне в голову - это TSP, так как в TSP каждый узел "должен" пройти. Но сложность TSP слишком высока.
Могу ли я изменить TSP таким образом, чтобы я мог уменьшить его сложность до полинома, или у вас есть другие подходы к вопросу