Find ALL paths in a grid between 2 nodes

Question

I'm trying to find all the paths between 2 nodes in a grid, and the path has to go through all the node from start to end. Example (Start = S, End = E)

0 0 0
0 S 0
0 0 E

The answer for the above is 2 paths: (ignore the '.''s)

0-0-0
|.......|
0 S-0
|
0-0-E

0-0-0
|......|
0 S 0
|...|...|
0-0 E

I thought of using recursing, but gave that up due to the high overhead of each call...and decided to go with an iterative approach using a stack. (kind of like recursing but not...fixed memory overhead). The solution works great for grids of size (4x7), but tried it on an 8x8 grid...and it didn't finish in 4 hours...which sort of makes sense since the total number of possibilities is around 3**62 (approx), as each node that is not on the edge has 3 possible ways of traversal...and hence that solution fails.

I thought of splitting the 8x8 grid into 2, using a vertical and horizontal split...but this would lead to finding less than ideal paths.

Is there something that I'm missing???? Can something be done to make it go faster? I will post the solution that I have tomorrow (done in C).

Answer 1

Have a look at the shortest paths problem it should get you started on this. The Bellmann-Ford or Dijkstra's algorithm are worth trying. You might be able to improve on the efficiency of those if your grid has some properties you can exploit.

Answer 2

Nope, you do not miss anything and nothing can be done faster.

This is the Longest Path Problem which is NP-Hard.