Шаг первый: устранить все циклы. Вы можете найти цикл, выбрав любой узел и сделав DFS. Если вы не найдете цикл, найдите другой узел, который вы не видели в предыдущей DFS, и выполните DFS с этого узла. Если вы обнаружите, что цикл сворачивает все узлы в один. В основном, если вы достигнете любого из узлов цикла, вы пройдете цикл, чтобы получить все веса. Поскольку вы можете повторно использовать узлы и края, вы всегда сможете продолжить свой путь по-прежнему. После того, как вы нашли цикл, повторите алгоритм, пока вы не свернете все циклы.
Шаг второй: найдите путь через свернутый граф. Теперь нет циклов, поэтому вы можете использовать Bellman Ford и найти самый длинный маршрут (вам нужно изменить условия, чтобы искать более длинные пути вместо более коротких). Поскольку каждый свернутый узел имеет весовой коэффициент цикла, который он представляет, вы получаете вес, который вы ищете. Если вы хотите восстановить путь, вам также нужно посмотреть на свернутые циклы и развернуть их на месте, позаботясь о добавлении пути из входной точки в точку выхода в цикле (скажем, у вас есть цикл с 10 узлами , край ввода переходит к узлу 1, но край выхода идет от узла 5, поэтому вам нужно добавить весь цикл 1,2,3,4,5 .. 10, начиная с входного края, а затем добавить часть цикла что приведет вас к краю выхода, в данном случае 1,2,3,4,5).
Сложность - O (N^2). DFS - это O (N) (включая выбор других узлов в случае, если вы не найдете их из текущего), и каждый раз, когда вы удаляете хотя бы один узел (вы не можете иметь цикл с одним узлом), поэтому вы будете запускать это не более N раз. Алгоритм BellmanFord также O (N^2). Реконструкция должна быть не более O (N).
и в чем вопрос и что вы достигли до сих пор? – mikus
@mikus Вопрос в том, как это можно сделать в сложное время. На данный момент я совершенно не знаю, и я понятия не имею, как подойти к этой проблеме. – Andrew