Как в сетке (nxn) найти k, k + 1, k + 2 путей из одной точки в другую?

Question

Рассмотрим сетку (матрица с n = 3):

0 1 2
3 4 5
6 7 8

Мне нужно найти k+1, k+2 пути между любой точкой к любой точке (здесь от 3 до 2),где k - кратчайшее расстояние или количество прыжков (k=3).Как мне найти пути dist k=4 или k=5?

У меня есть программа (в java) для поиска всех путей k:

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используя формулу расстояния, я могу ограничить количество вертикальных и горизонтальных перемещений и использовать рекурсию, чтобы найти все точки на кратчайшем пути.Может кто-нибудь предложить что-то подобное для путей с dist> 3?

Answer 1

Игнорировать тот факт, что это сетка.Просто рассмотрите это как график.У вас есть очки.У каждой точки есть соседи.Каждая точка имеет минимальное расстояние до конечной точки.Вот немного Python для демонстрации алгоритма.(Перевод на Java не должен быть сложным.)

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

В качестве существенной оптимизации вы можете заметить, что в вашем случае все пути от p1 до p2 имеют одинаковую длину mod 2. Поэтому для длиныk + i вообще нет путей, если i не является четным.

Answer 2

Вы можете посмотреть алгоритм Джонсона, часть I и часть II , который перечисляет все элементарные схемы (циклы) в ориентированном графе.