Pathfinding in adjacency matrix

Question

Given an adjacency matrix, how would you find the shortest paths between two nodes while traversing to each point at least once and returning how many moves it takes?

Example

Given this array

int[][] points = { { 0, 1 },{ 0, 2 },{ 1, 2 },{ 1, 3 },{ 3, 4 } };

I make an adjacent matrix like so...

     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]

The shortest path from 0 - 4 is (0-2)(2-1)(1-3)(3-4) and counts to be 4 moves.

I really have no idea how to go any further. Possibly a minimum spanning tree solution? Thanks in advance.

Traversing to each point at least once -> Sounds similar to a [Hamiltonian path](http://en.wikipedia.org/wiki/Hamiltonian_path), which is not an easy problem to solve efficiently. — Bernhard Barker, Apr 07 '13 at 23:53
[Johnson's algorithm](http://en.wikipedia.org/wiki/Johnson%27s_algorithm) is examined [here](http://stackoverflow.com/q/2939877/230513). — trashgod, Apr 07 '13 at 23:53
@trashgod, but we need to visit every vertex at least once. Johnsons algorithm runs in poly time, but it seems this may be related to some NP Hard problems (not quite if all edge weights are 1). Maybe im missing something though. — Anil Vaitla, Apr 07 '13 at 23:56
This sounds simpler than the Hamiltonian Path problem (since we can visit vertices multiple times -> deciding whether such a path exists can be done by checking the graph for connectivity). It doesn't actually feel simpler though. — G. Bach, Apr 08 '13 at 00:45
@G.Bach But if our algorithm returns a path of size |V| - 1 (over all pairs of O(n^2) verts), isn't that answering decidability version of Hamiltonian path, or am I missing something? — Anil Vaitla, Apr 08 '13 at 01:14
@tigger I didn't think of that, you are correct, this is then at least as difficult as the HP problem. But I think it would be clearer to say that if an HP exists, any algorithm solving mjenkins's problem must return an HP. — G. Bach, Apr 08 '13 at 01:24

Anil Vaitla · Answer 1 · 2013-04-08T00:24:28.180

Pretty sure this is NP Hard by reduction to Hamiltonian Path Problem as suggested by Dukeling. Suppose we have a poly time algorithm X to solve this problem. Then that means we can ask X the question of finding a minimum length path between any 2 vertices which visits all other vertices on the way to the end.

Now since we need to visit all vertices at least once, this means that the minimum length of such a path is (|V| - 1). So if our algorithm gives us a path of size (|V| - 1), we have answered the decidability problem of Hamiltonian path in poly time because we may run our algorithm X on all pairs of vertices (of which there are O(n^2)) in poly time as well.

There may be a way to use dynamic programming / recursion, but I cannot prove it is poly time. The shortest path from s to t, that visits all vertices can be computed by looking at the graph G/{s}, and ask given i \in Neighbors(s), what the shortest path from i to t is. Then we know that the shortest path from s to t, must be equal to s appended to one of its neighbors (specifically the one that leads to the shortest path to t).

It shouldn't be considering this was a assignment for class. Was* meaning that its already turned in. I'm just trying to figure out how to do it for a learning experience. — mjenkins2010, Apr 08 '13 at 00:10
Okay, I must be missing something. I'll have to think further. Can you see what I my argument is missing? That might help us find the right course of action. — Anil Vaitla, Apr 08 '13 at 00:12

Pathfinding in adjacency matrix

1 Answers1