通过所有其他节点从节点 A 到 B 的最短路径（NP-Hard？）
Shortest Path from Node A to B by going through all other Nodes (NP-Hard?)
我的问题：找到从节点 A 到节点 B 的最短路径，该路径通过未加权的有向图的所有其他节点。我知道有这么一条路。
我相信这是 NP-Hard，但我无法解释。我的教授喜欢让算法在 O(|V| + |E|) 的运行时执行，其中 V 是节点集，E 是边集。
好像和this problem差不多，但是Graph的属性不一样，有区别吗？
是的，它是 NP 难的。如果你的求解器 运行 在 P 中，那么通过 运行 它在每一对点上你都会有一个 P 时间求解器 Hamiltonian Path.
answer you linked给出了更严格的证明
我的问题：找到从节点 A 到节点 B 的最短路径，该路径通过未加权的有向图的所有其他节点。我知道有这么一条路。
我相信这是 NP-Hard，但我无法解释。我的教授喜欢让算法在 O(|V| + |E|) 的运行时执行，其中 V 是节点集，E 是边集。
好像和this problem差不多，但是Graph的属性不一样，有区别吗？
是的，它是 NP 难的。如果你的求解器 运行 在 P 中，那么通过 运行 它在每一对点上你都会有一个 P 时间求解器 Hamiltonian Path.
answer you linked给出了更严格的证明