最长的简单路径

Question

因此,我理解在图中找到最长的简单路径的问题是NP难的,因为您可以通过将边权重设置为1并查看最长简单路径的长度是否等于数量来轻松解决哈密顿电路问题.边缘.

我的问题是:如果你采用图表,找到最大边缘权重m,用每个边缘权重w替换m - w,并运行标准的最短路径算法,你会得到什么样的路径？它显然不是最长的简单路径,因为如果是,那么NP = P,我认为类似的东西的证明会更复杂= P.

Answer 1

替代文本 http://dl.getdropbox.com/u/317805/path2.jpg

使用您的算法将上图转换为下图。

最长路径是上图中的红线。根据关系的断开方式和您使用的算法，转换后的图中的最短路径可能是蓝线或红线。因此，使用您提到的常量转换图边权重不会产生显着的结果。这就是为什么无论你多么聪明，你都无法使用最短路径算法找到最长路径。更简单的转换可能是否定所有边权重并运行算法。我不知道我是否回答了您的问题，但就路径属性而言，转换后的图形没有任何有关距离的有用信息。

然而，这种特殊的转变在其他领域也很有用。例如，如果您有多个约束，则可以通过添加一个巨大的常量来强制算法在二元匹配中选择特定的边权重。

• 编辑：我被告知要添加以下声明：上图不仅仅是关于物理距离。他们不需要保持三角不等式。谢谢。