通过所有其他节点（NP-Hard？）从节点A到B的最短路径

Question

我的问题：找到从节点A到节点B的最短路径，该节点通过未加权的直接图形的所有其他节点。我知道存在这样一条路。

我相信这是NP-Hard，但我无法解释它。我的教授喜欢让算法在O(|V| + |E|)的运行时间上执行，其中V是一组节点和E边缘集合。

看起来它与this problem类似，但Graph的属性不同，它有什么区别吗？

Answer 1

是的，它是NP-hard。如果你的求解器在P中运行，那么通过在每对点上运行它，你将有一个P时间求解器Hamiltonian Path。

answer you linked给出了更严格的证明。