我的问题：找到从节点A到节点的最短路径，该路径B通过未加权直接图的所有其他节点。我知道存在这样的路径。
我相信这是 NP-Hard，但我无法解释。我的教授喜欢让算法在 的运行时执行O(|V| + |E|)，其中V是节点E集和边集。
好像和这个问题差不多，但是Graph的属性不一样，有区别吗？
问问题
291 次
1 回答
1
是的，它是 NP 难的。如果您的求解器在 P 中运行，那么通过在每一对点上运行它，您将获得Hamiltonian Path的 P 时间求解器。
您链接的答案提供了更严格的证明。
于 2017-06-12T15:55:48.143 回答