在邻接矩阵中寻找路径

Question

给定一个邻接矩阵，如何找到两个节点之间的最短路径，同时遍历每个点至少一次并返回它需要的移动次数？

例

鉴于这种阵列

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次移动。

我真的不知道如何去更进一步。可能是最小生成树解决方案？提前致谢。

Answer 1

很确定这是NP Hard通过减少哈密顿路径问题，正如Dukeling所建议的那样。假设我们有一个多时间算法X来解决这个问题。那么这意味着我们可以问X找到在到达结束的路上访问所有其他顶点的任何2个顶点之间的最小长度路径的问题。

现在由于我们需要访问所有顶点至少一次，这意味着这种路径的最小长度是（| V | -1）。因此，如果我们的算法给出了一个路径的大小（| V | -1），我们已经回答了多时间哈密顿路径的可判定性问题，因为我们可以在所有的顶点对（其中有O（n^2））在多时间以及。

可能有办法使用动态编程/递归，但我不能证明它是多时间。从s到t的最短路径可以通过查看图G/{s}来计算，并且在邻居中询问给定的i，从i到t的最短路径是什么。那么我们知道从s到t的最短路径必须等于s附加到它的一个邻居（特别是通向t的最短路径）。