In a Grid(nxn), how to find k,k+1,k+2 paths from one point to another point?

Question

Consider the grid (a matrix with n=3):

0 1 2
3 4 5
6 7 8

I need to find k+1,k+2 paths between any point to any point (here from 3 to 2),where k is the shortest distance or number of hops (k=3). How do I go about find paths of dist k=4 or k=5?

I have a program (in java) for finding all the k paths :

public ArrayList<Path> findPath(int y1, int x1, int y2, int x2){

       int vert = y1-y2;//1
       int hori = x1-x2;//-2
       int max = (vert > 0 ? vert : -vert)+(hori > 0 ? hori : -hori);

       return findPath(y1,x1,vert,hori,vert,hori,0,max);
    }

    public ArrayList<Path> findPath(int y, int x, int vert, int hori, int v, int h, int level, int max){
       if(level > max){
           System.exit(1);
       }
       System.out.println(y+","+x+","+vert+","+hori+","+v+","+h);
       ArrayList<Path> ret = new ArrayList<Path>();
       if(v == 0 && h == 0){
           ret.add(new Path());
           ret.get(0).pushPath(network[y][x]);
           return ret;
       }

       int vm = vert > 0 ? -1 : 1;//-1
       int hm = hori > 0 ? -1 : 1;//1
       System.out.println(vm+","+hm);

       ArrayList<Path> a = new ArrayList<Path>();
       if(v!=0){ a = findPath(y+vm, x, vert, hori, v+vm, h, level+1, max); }

       ArrayList<Path> b = new ArrayList<Path>();
       if(h!=0){ b = findPath(y, x+hm, vert, hori, v, h+hm, level+1, max); }

       for(Path p : a){
           p.pushPath(network[y][x]);
          }

       for(Path p : b){
           p.pushPath(network[y][x]);
       }

       ret = new ArrayList<Path>(a);
       ret.addAll(b);
       return ret;  

     }

By using the distance formula, I am able to restrict the number of vertical and horizontal movements and use recursion to find all the points in the shortest path. Can someone please suggest something similar for paths with a dist >3?

Answer 1

You might look a the Johnson algorithm, part I and part II, which enumerates all the elementary circuits (cycles) in a directed graph.

Answer 2

Ignore the fact that it is a grid. Just consider it as a graph. You have points. Each point has neighbors. Each point has a minimum distance to the final point. Here is some Python to demonstrate an algorithm. (Translation to Java should not be hard.)

def paths(p1, p2, length):
    answer = []
    if 0 == length and p1 == p2:
        answer = [p1]
    elif length <= distance(p1, p2):
        for p in neighbors(p1):
            answer.extend([ [p1] + x for x in paths(p, p2, length-1) ])
    return answer

As a significant optimization you may note that in your case all paths from p1 to p2 have the same length mod 2. Therefore for length k + i there are no paths at all unless i is even.