Самый длинный путь в взвешенном неориентированном графе

Question

Мне нужно найти самый длинный путь на графике на основе веса ребер.Для графика на изображении это должно быть 4,5,3,2,1 (порядок не имеет значения). Каков наилучший алгоритм для решения этой проблемы?Что если вы знаете, что на вашем графике каждый узел имеет ссылку (ребро) на любой другой узел на графике.Должен ли алгоритм быть изменен?

Answer 1

Найти самый длинный путь в графе - задача NP-Complete.Вопреки распространенному мнению, это не означает, что это не может быть решено за полиномиальное время (на самом деле это одна из величайших нерешенных проблем в информатике P против NP ).Тем не менее, это означает, что это по крайней мере так же сложно, как самые сложные проблемы в NP.Другими словами, может быть эффективный алгоритм для решения этой проблемы, но пока никто не смог его найти.По сути, это невозможно решить эффективно.Знание того, что каждый узел имеет преимущество перед каждым другим узлом, не меняет того факта, что эта проблема является NP-полной.

Answer 2

• Самая длинная проблема пути - NP-complete , что означает, что ее невозможно решить за полиномиальное время .
• Для направленных ациклических графов оно имеет линейное решение, но поскольку речь идет о неориентированных графах, это не сработает.
• A «действительным» решением может быть просто грубая сила графика путем многократного обхода глубина-в-первых , чтобы сгенерировать все возможные пути от А доB. Когда вы сгенерировали все пути, найдите тот, который имеет максимальное расстояние.