Первым шагом является превращение двунаправленных ребер в направленные ребра, переходя только от меньшего к большему пронумерованному узлу для каждого. Обратите внимание, что результирующий граф будет ориентированным ациклическим графом (DAG), поскольку мы не можем перейти от небольшого-высокого-малого числа в пути. С этого момента мы можем игнорировать нумерацию узлов.
Теперь мы уменьшили проблему до проблема самого длинного пути . Решение (подробно описано в ссылке) состоит в том, чтобы выполнить топологическую сортировку на графе и затем использовать динамическое программирование, чтобы найти самый длинный путь.
Все это может быть достигнуто за линейное время.