Using recursion to find paths in a 2D array

Question

Hi, I'm working on a project for my A level. It involves finding the maximum flow of a network, and I'm using javascript.

I have a 2D array, with values in the array representing a distance between the two points. An example of the array:

0 2 2 0
0 0 1 2
0 0 0 2
0 0 0 0

I think I need to use a recursive technique to find a path; below is some pseudocode, assuming that the array is 4x4. a is (0,0), b is (3,3).

function search(a,b)
  from a to b
    if element(i,j) != 0 then
      store value of element
      search(j,3)

I was wondering if that was the right construction for a depth first search. Thanks for any help.

Answer 1

Seriously consider using BFS. Edmonds-Karp is the Ford-Fulkerson but the path finding method is fixed - BFS, which guarantees worst case O(V * E^2), which is not the case with DFS. V is number of vertices and E - number of edges. If you still insist on DFS, then at least you should check that the node which you are visiting next in the loop is not yet visited to prevent eternal recursion. You can use a boolean array for it.

Answer 2

Pathfinding can be easily achieved by using the floodfill algorithm, which can be written in a recursive form as

function floodFill(x, y, prevPoints)
{
 var prevPoints = prevPoints.concat([]); //make a copy of the points list since JS uses ref

 if(grid[x][y].isExit) return prevPoints;
 grid[x][y].accessed = true;
 prevPoints.push([x, y]);

 var result;
 var cfr; //cellfillresult
 if(grid[x+1][y].isPath && !grid[x+1][y].accessed) cfr = floodFill(x+1, y, prevPoints);
 if(cfr != null) result = cfr;

 if(grid[x-1][y].isPath && !grid[x-1][y].accessed) cfr = floodFill(x-1, y, prevPoints);
 if(cfr != null) result = cfr;

 if(grid[x][y+1].isPath && !grid[x][y+1].accessed) cfr = floodFill(x, y+1, prevPoints);
 if(cfr != null) result = cfr;

 if(grid[x][y-1].isPath && !grid[x][y-1].accessed) cfr = floodFill(x, y-1, prevPoints);
 if(cfr != null) result = cfr;

 return result;
}

var pathToExit = floodFill(entranceX, entranceY, []);  

However, this is highly inefficient and will cause a stack overflow once you get to larger-ish grids... A better way to do this would be to make a software stack...

Also, it only finds a path that works, but not the most efficient path. You'll have to add counting to the algorithm [which shouldn't take too much effort, hopefully]