最长的简单路径

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

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