algorithm - 加权无向图中的最长路径

Question

我需要根据边权重在图中找到最长的路径。对于图像上的图形，它应该是 4,5,3,2,1(顺序无关紧要)解决这个问题的最佳算法是什么？如果你知道在你的图中，每个节点都有一个对图中任何其他节点的引用(边)。算法应该改变吗？

Answer 1

• 最长路径问题是NP-complete这意味着它 cannot be solved in polynomial time .
• 对于有向无环图，它有一个线性解，但由于问题是关于无向图，所以这行不通。
• “有效” 解决方案可以是通过以深度优先方式按顺序多次遍历来简单地暴力图形生成从 A 到 B 的所有可能路径。生成所有路径后，找到距离最大的路径。