在鄰接矩陣中尋找路徑

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的最短路徑）。