给定一个邻接矩阵，你如何找到两个节点之间的最短路径，同时至少遍历每个点一次并返回它需要多少次移动？
例子
给定这个数组
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 步。
我真的不知道如何走得更远。可能是最小生成树解决方案？提前致谢。
正如杜克林所建议的那样，通过简化为哈密顿路径问题，可以肯定这是 NP Hard。假设我们有一个多时间算法 X 来解决这个问题。那么这意味着我们可以问 X 寻找在任何 2 个顶点之间的最小长度路径的问题，该路径在到达终点的过程中访问所有其他顶点。
现在，由于我们需要至少访问所有顶点一次，这意味着这样一条路径的最小长度是 (|V| - 1)。因此，如果我们的算法给了我们一条大小为 (|V| - 1) 的路径，我们已经在多时间内回答了哈密顿路径的可判定性问题，因为我们可以在所有顶点对上运行我们的算法 X（其中有 O(n ^2)) 在多时间也是如此。
可能有一种使用动态编程/递归的方法，但我无法证明它是多时间。访问所有顶点的从 s 到 t 的最短路径可以通过查看图 G/{s} 来计算，并询问给定 i \in Neighbors(s)，从 i 到 t 的最短路径是什么。然后我们知道从 s 到 t 的最短路径必须等于 s 附加到它的邻居之一（特别是通向 t 的最短路径的那个）。