Создание полного списка допустимых путей с помощью рекурсии

Нет никакой причины использовать A *. Он предназначен для максимально эффективного поиска кратчайшего пути. Если вы хотите найти все пути независимо от длины, A * будет накладными расходами без каких-либо преимуществ.

В псевдокоде ваш алгоритм должен выглядеть примерно так:

findPaths for path:
    if path is complete
        add to solution set
    else
        for each link from last step that is not in path
            add next step to path
            call findPaths
            remove next step from path

В настоящий момент вы возвращаете путь. Если вы хотите найти все пути, вам нужно сохранить их в списке путей.

Вот пример реализации:

public class FindPath {
    private final Stack<Integer> path = new Stack<>();
    private final Map<Integer, Set<Integer>> links = new HashMap<>();

    public void addLink(int from, int to) {
        links.putIfAbsent(from, new HashSet<>());
        links.get(from).add(to);
    }

    public void find(int from, int to, Consumer<Stack<Integer>> action) {
        path.push(from);
        if (from == to)
            action.accept(path);
        else
            links.getOrDefault(from, Set.of()).stream()
                    .filter(s -> !path.contains(s))
                    .forEach(s -> find(s, to, action));
        path.pop();
    }

    public static void main(String[] args) {
        FindPath finder = new FindPath();
        Random rand = new Random();
        IntStream.range(0, 20).forEach(n -> rand.ints(7, 0, 20).forEach(t -> finder.addLink(n, t)));
        finder.find(0, 19, System.out::println);
    }
}

Вы можете изменить мой исходный код, чтобы вернуть все пути в виде списка, как вы просили. Только не возвращай код раньше срока. Однако это не будет сортироваться по длине пути. Если вы этого хотите, вам понадобится A *.

public List<List<Integer>> searchHops(int from, int to, Set<Integer> seen) {
    seen.add(from);

    if (from == to) {
        final List<List<Integer>> newList = new ArrayList<>();
        newList.add(new ArrayList<>(Arrays.asList(from)));
        return newList;
    }

    List<List<Integer>> allPaths = null;
    for (int neighbor : getNeighbors(from)) {
        if (!seen.contains(neighbor)) {
            List<List<Integer>> results = searchHops(neighbor, to, new HashSet<>(seen));

            if (results != null) {
                for(List<Integer> result : results) {
                    result.add(0, from);
                    if ( allPaths != null )
                        allPaths.add(result);
                }
                if ( allPaths == null )
                    allPaths = results;
            }
        }
    }
    return allPaths;
}

Если вы действительно заботитесь о том, чтобы упорядочить свои пути от кратчайшего пути к самому длинному пути, было бы гораздо лучше использовать A *. A * вернет столько возможных путей, сколько вы хотите, в порядке кратчайшего пути. Итак, если вам действительно нужны все возможные пути, упорядоченные от самого короткого до самого длинного, вам все равно нужен алгоритм A *. Код, который я предложил выше, будет намного медленнее, чем должен быть, если вы заботитесь о порядке от самого короткого к самому длинному, не говоря уже о том, что он займет больше места, чем вы хотели бы, чтобы сохранить все возможные пути сразу.

Поскольку вы указали, что сначала заботитесь о кратчайшем пути и, возможно, захотите получить N-кратчайшие пути, вам обязательно следует использовать здесь A *.

Если вам нужна реализация на основе A *, способная возвращать все пути, упорядоченные от самого короткого до самого длинного, это выполнит следующее. У него есть несколько преимуществ. Во-первых, он эффективен при сортировке от самого короткого до самого длинного. Кроме того, он вычисляет каждый дополнительный путь только при необходимости, поэтому, если вы остановитесь раньше, потому что вам не нужен каждый отдельный путь, вы сэкономите время обработки. Он также повторно использует данные для последующих путей каждый раз, когда вычисляет следующий путь, что делает его более эффективным. В целом алгоритм должен быть наиболее эффективным, если вы заботитесь о сортировке по длине пути.

import java.util.*;

public class AstarSearch {
    private final Map<Integer, Set<Neighbor>> adjacency;
    private final int destination;

    private final NavigableSet<Step> pending = new TreeSet<>();

    public AstarSearch(Map<Integer, Set<Neighbor>> adjacency, int source, int destination) {
        this.adjacency = adjacency;
        this.destination = destination;

        this.pending.add(new Step(source, null, 0));
    }

    public List<Integer> nextShortestPath() {
        Step current = this.pending.pollFirst();
        while( current != null) {
            if ( current.getId() == this.destination )
                return current.generatePath();
            for (Neighbor neighbor : this.adjacency.get(current.id)) {
                if (!current.seen(neighbor.getId())) {
                    final Step nextStep = new Step(neighbor.getId(), current, current.cost + neighbor.cost + predictCost(neighbor.id, this.destination));
                    this.pending.add(nextStep);
                }
            }
            current = this.pending.pollFirst();
        }
        return null;
    }

    protected int predictCost(int source, int destination) {
        return 0; //Behaves identical to Dijkstra's algorithm, override to make it A*
    }

    private static class Step implements Comparable<Step> {
        final int id;
        final Step parent;
        final int cost;

        public Step(int id, Step parent, int cost) {
            this.id = id;
            this.parent = parent;
            this.cost = cost;
        }

        public int getId() {
            return id;
        }

        public Step getParent() {
            return parent;
        }

        public int getCost() {
            return cost;
        }

        public boolean seen(int node) {
            if (this.id == node)
                return true;
            else if (parent == null)
                return false;
            else
                return this.parent.seen(node);
        }

        public List<Integer> generatePath() {
            final List<Integer> path;
            if (this.parent != null)
                path = this.parent.generatePath();
            else
                path = new ArrayList<>();
            path.add(this.id);
            return path;
        }

        @Override
        public int compareTo(Step step) {
            if (step == null)
                return 1;
            if ( this.cost != step.cost)
                return Integer.compare(this.cost, step.cost);
            if ( this.id != step.id )
                return Integer.compare(this.id, step.id);
            if ( this.parent != null )
                this.parent.compareTo(step.parent);
            if (step.parent == null)
                return 0;
            return -1;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Step step = (Step) o;
            return id == step.id &&
                cost == step.cost &&
                Objects.equals(parent, step.parent);
        }

        @Override
        public int hashCode() {
            return Objects.hash(id, parent, cost);
        }
    }

   /*******************************************************
   *   Everything below here just sets up your adjacency  *
   *   It will just be helpful for you to be able to test *
   *   It isnt part of the actual A* search algorithm     *
   ********************************************************/

    private static class Neighbor {
        final int id;
        final int cost;

        public Neighbor(int id, int cost) {
            this.id = id;
            this.cost = cost;
        }

        public int getId() {
            return id;
        }

        public int getCost() {
            return cost;
        }
    }

    public static void main(String[] args) {
        final Map<Integer, Set<Neighbor>> adjacency = createAdjacency();
        final AstarSearch search = new AstarSearch(adjacency, 1, 4);
        System.out.println("printing all paths from shortest to longest...");
        List<Integer> path = search.nextShortestPath();
        while(path != null) {
            System.out.println(path);
            path = search.nextShortestPath();
        }
    }

    private static Map<Integer, Set<Neighbor>> createAdjacency() {
        final Map<Integer, Set<Neighbor>> adjacency = new HashMap<>();

        //This sets up the adjacencies. In this case all adjacencies have a cost of 1, but they dont need to. Otherwise
        //They are exactly the same as the example you gave in your question
        addAdjacency(adjacency, 1,2,1,5,1);         //{1 | 2,5}
        addAdjacency(adjacency, 2,1,1,3,1,4,1,5,1); //{2 | 1,3,4,5}
        addAdjacency(adjacency, 3,2,1,5,1);         //{3 | 2,5}
        addAdjacency(adjacency, 4,2,1);             //{4 | 2}
        addAdjacency(adjacency, 5,1,1,2,1,3,1);     //{5 | 1,2,3}

        return Collections.unmodifiableMap(adjacency);
    }

    private static void addAdjacency(Map<Integer, Set<Neighbor>> adjacency, int source, Integer... dests) {
        if ( dests.length % 2 != 0)
            throw new IllegalArgumentException("dests must have an equal number of arguments, each pair is the id and cost for that traversal");

        final Set<Neighbor> destinations = new HashSet<>();
        for(int i = 0; i < dests.length; i+=2)
            destinations.add(new Neighbor(dests[i], dests[i+1]));
        adjacency.put(source, Collections.unmodifiableSet(destinations));
    }
}

Результатом приведенного выше кода является следующее:

[1, 2, 4]
[1, 5, 2, 4]
[1, 5, 3, 2, 4]

Обратите внимание, что каждый раз, когда вы вызываете nextShortestPath(), он по запросу генерирует для вас следующий кратчайший путь. Он только рассчитывает необходимые дополнительные шаги и не пересекает старые пути дважды. Более того, если вы решите, что вам не нужны все пути и завершите выполнение раньше, вы сэкономите значительное время на вычисления. Вы вычисляете только то количество путей, которое вам нужно, и не более того.

Если у вас есть какая-то эвристика, которая помогает оценить стоимость пути, переопределите метод predictCost() и поместите его туда. Вы упомянули, что ваши узлы также имеют связанные с ними пространственные координаты. Хорошей эвристикой в ​​этом случае будет евклидово расстояние между двумя узлами (расстояние между ними будет прямой линией). Однако это полностью вариант и помогает сократить время вычислений только в том случае, если вы выйдете до вычисления всех возможных путей.

Наконец, следует отметить, что алгоритмы A * и Dijkstra имеют некоторые незначительные ограничения, хотя я не думаю, что это повлияет на вас. А именно, это не будет работать правильно на графике с отрицательными весами.

Вот ссылка на JDoodle, где вы можете запустить код самостоятельно в браузере и увидеть, как он работает. Вы также можете изменить график, чтобы показать, что он работает и на других графиках: http://jdoodle.com/a/ukx