加权无向图中的最长路径
Longest Path in a weighed non directed graph
我需要根据边的权重在图中找到最长的路径。对于图像上的图形，它应该是 4,5,3,2,1（顺序无关紧要）解决这个问题的最佳算法是什么？如果你知道在你的图中，每个节点都有一个对图中任何其他节点的引用（边）。是否应该更改算法？
- 最长路径问题是NP-complete which means that it cannot be solved in polynomial time。
- 对于有向无环图它有一个线性解，但是由于问题是关于无向图，所以这行不通。
- A "valid" 解决方案可以通过遍历 来简单地暴力 图形多次深度优先方式，以生成从A到B的所有可能路径。生成所有路径后，找到距离最大的路径。
寻找图中的最长路径是一个 NP 完全问题。与流行的看法相反，这并不意味着它不能在多项式时间内解决（事实上，这是计算机科学中未解决的重大问题之一 P vs NP）。然而，这确实意味着它至少和 NP 中最难的问题一样难。换句话说，可能有一种高效的算法可以解决这个问题，但目前还没有人能够找到它。实际上不可能有效地解决。知道每个节点到每个其他节点都有边并不会改变这个问题是 NP 完全问题的事实。
我需要根据边的权重在图中找到最长的路径。对于图像上的图形，它应该是 4,5,3,2,1（顺序无关紧要）解决这个问题的最佳算法是什么？如果你知道在你的图中，每个节点都有一个对图中任何其他节点的引用（边）。是否应该更改算法？
- 最长路径问题是NP-complete which means that it cannot be solved in polynomial time。
- 对于有向无环图它有一个线性解，但是由于问题是关于无向图，所以这行不通。
- A "valid" 解决方案可以通过遍历 来简单地暴力 图形多次深度优先方式，以生成从A到B的所有可能路径。生成所有路径后，找到距离最大的路径。
寻找图中的最长路径是一个 NP 完全问题。与流行的看法相反，这并不意味着它不能在多项式时间内解决（事实上，这是计算机科学中未解决的重大问题之一 P vs NP）。然而，这确实意味着它至少和 NP 中最难的问题一样难。换句话说，可能有一种高效的算法可以解决这个问题，但目前还没有人能够找到它。实际上不可能有效地解决。知道每个节点到每个其他节点都有边并不会改变这个问题是 NP 完全问题的事实。