Мне нужна помощь, чтобы решить этот вопрос:
у вас есть граф G = (V, E), пара узлов s ≠ t ∈ V и у вас есть подмножество узлов U ⊆ V, которое существует ø ≠ UAnd V и s, t ∉ U. для каждого пути P мы отмечаем его L (P) длину пути (количество ребер в пути) и #P (U) количество узлов U в пути, пишемАлгоритм нахождения пути между s и t, который должен посетить U ровно в 2 раза и минимальной длиной всех этих дорожек.Другими словами, алгоритм должен возвращать путь от s до t, где #P (U) = 2, и, допустим, у нас есть другой путь P 'от s до t, где #P' (U) = 2, тогда L (P) ≤ L(P ') (допустимо, чтобы трек проходил через определенную вершину более одного раза).Справка: используйте сокращение графов G '