Найти самый длинный путь в графе, где каждый узел имеет не более двух входящих и двух исходящих ребер

Question

Как видно из заголовка, я должен найти самый длинный путь в ориентированном графе, где каждый узел имеет не более двух входящих ребер и двух исходящих ребер. Я не знаю, поможет ли этот факт чему-нибудь. График будет содержать не более 10000 узлов. И мне нужно найти самый длинный путь от узла 0 к узлу "Выход", который будет 10001.

Я пытался закодировать dijkstra, но это не сработало.

Заранее спасибо.

Answer 1

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