-3

I have a grid of NxN cells (think of a 2 dimensional array defined as follows Array[N][N]).

Which algorithm will compute every path from every cell a[i][j] to every cell a[k][l] where:

  1. No cell is included twice within a single path.
  2. Only adjacent diagonal, horizontal and vertical moves all legal.
  3. The algorithm is the fastest, on average.
  4. The least amount of memory is used.
TheOne
  • 10,819
  • 20
  • 81
  • 119
  • Good question. Seems like a dynamic programming problem. – aioobe May 08 '12 at 11:28
  • I would change `5 by 5` to `N by N` before someone answer with an algorithm with a pre-calculated hard-coded answer. – aioobe May 08 '12 at 11:29
  • 1
    Djkistra's shortest path algorithm I'd imagine, take a quick look here for more information, it might help you come up with a solution. http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm – David K May 08 '12 at 11:33
  • This sounds like a variation of the travelling salesman problem making it NP Complete and requiring a brute-force solution. You need to me more specific about the rules. Are you allowed to move diagonally (0,0 --> 1,1)? Can you skip cells (0,0 -> 2,0)? – David Buck May 08 '12 at 11:39
  • 1
    "3. The algorithm is the fastest, on average. 4. The least amount of memory is used." This kind of "requirement" is meaningless. The fastest and the most space-efficient algorithm are usually not the same algorithm. – svinja May 08 '12 at 12:09

2 Answers2

1

The breadth-first search will do exactly what you want. When generating all paths there's no fastest

t3hn00b
  • 904
  • 5
  • 13
  • 1
    How will breadth-first search *all* paths. It typically terminates one path when it reaches a node which is already in the *visited* set. – aioobe May 08 '12 at 11:30
  • http://stackoverflow.com/questions/713508/find-the-paths-between-two-given-nodes/713579#713579 – t3hn00b May 08 '12 at 11:38
  • I am sorry, but BFS without modifications will fail to find all paths. For example: find paths between (0,0) and (1,2): assume BFS yields the feasible path `(0,0)->(1,1)->(1,2)`, then it will not yield `(0,0)->(1,0)->(0,1)->(1,1)->(1,2)`, since BFS maintains `visited` set, and thus `(1,1)` will not be re-explored in the second path. If you have specific modification to BFS - please explain it with details, as standard BFS fails here. – amit May 08 '12 at 12:13
  • Will get back to you later for the BFS solution - for now I've found in my lectures this source - recursive algorithm for finding all paths - http://pastebin.com/V0wNEpqY - it's publicly available as part of Telerik Academy's lectures ( http://academy.telerik.com/academy/csharp-programming-fundamentals/resources ) – t3hn00b May 08 '12 at 12:34
  • @t3hn00b: The algorithm there is a DFS, not a BFS. – amit May 08 '12 at 19:14
0

I assume you want the actual paths, and not just the number of them.

You can achieve it by using DFS that maintains visited set on the vertices explored in the same path, and avoids exploring a vertex that was already discovered in the same path.

Pseudo code:

DFS(v,target,visited):
   if (v == target):
      print path to v from the initial sorce
      return
   visited.add(v)
   for each vertex u such that u is a neighbor of v:
      if (u is not in visited):
          u.parent <- v
          DFS(u,target,visited)
   visited.remove(v)

invoke with DFS(source,target,{}) [where {} is an empty visited set].

amit
  • 175,853
  • 27
  • 231
  • 333