给定一个邻接矩阵，你如何找到两个节点之间的最短路径，同时至少遍历一个点并返回它需要多少次移动？
Example
鉴于此数组
int[][] points = { { 0, 1 },{ 0, 2 },{ 1, 2 },{ 1, 3 },{ 3, 4 } };
我像这样制作一个相邻的矩阵......
0 1 2 3 4
0 [0] [1] [1] [0] [0]
1 [1] [0] [1] [1] [0]
2 [1] [1] [0] [0] [0]
3 [0] [1] [0] [0] [1]
4 [0] [0] [0] [1] [0]
从0到4的最短路径是（0-2）（2-1）（1-3）（3-4）并且计数为4次移动 .
我真的不知道如何进一步 . 可能是最小的生成树解决方案？提前致谢 .
1 回答
很确定这是NP Hard通过减少到Dukeling建议的哈密尔顿路径问题 . 假设我们有一个多时间算法X来解决这个问题 . 那么这意味着我们可以问X在任何2个顶点之间找到最小长度路径的问题，这两个顶点在到达终点的路上访问所有其他顶点 .
现在因为我们需要至少访问所有顶点一次，这意味着这样一条路径的最小长度是（| V | - 1） . 因此，如果我们的算法为我们提供了一个大小的路径（| V | - 1），我们已经解决了聚合时间中哈密顿路径的可判定性问题，因为我们可以在所有顶点对上运行我们的算法X（其中有O（n） ^ 2））在聚合时间也是如此 .
可能有一种方法可以使用动态编程/递归，但我不能证明它是聚合时间 . 可以通过查看图G / 来计算从s到t的访问所有顶点的最短路径，并且在邻居中询问给定i \，从i到t的最短路径是什么 . 然后我们知道从s到t的最短路径必须等于附加到其邻居之一的s（特别是导致到t的最短路径的邻居） .