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