Как получить кратчайший путь между двумя узлами с помощью поиска в ширину?

Question

Я обновляю свои знания алгоритмов и структуры данных и хотел бы знать, может ли кто-нибудь помочь мне выяснить, как найти кратчайший путь между двумя узлами с помощью BFS. Пока что у меня есть следующий метод, который возвращает самую короткую часть на графике:

private Node[] nodes;

public static int[] shortestPath(Node source){
        LinkedList<Node> queue = new LinkedList<Node>();
        queue.add(source);

        int[] distances = new int[totalNodes];
        Arrays.fill(distances,-1);

        distances[source] = 0;

        while(!queue.isEmpty()){
            Node node = queue.poll();

            for (int neighbor: nodes[node].neighbor) {
                if(distances[neighbor] == -1) {
                    distances[neighbor] += distances[distanceIndex] + 1;
                    queue.add(neighbor);
                }

            }
        }
            return distances;
    }


}

Мне было интересно, как бы выглядело решение, если бы я хотел реализовать такой метод:

public static int[] shortestPath(Node source, Node destination){
// 
}

Заранее спасибо за помощь, я новичок в структурах данных и не знаю, как go об этом

Answer 1

private Node[] nodes;

public static int shortestPath(Node source, Node destination){
        LinkedList<Node> queue = new LinkedList<Node>();
        queue.add(source);

        int[] distances = new int[totalNodes];
        Arrays.fill(distances,-1);

        distances[source] = 0;

        while(!queue.isEmpty()){
            Node node = queue.poll();

            for (int neighbor: nodes[node].neighbor) {
                if(distances[neighbor] == -1) {
                    distances[neighbor] += distances[node] + 1;
                    queue.add(neighbor);

                    if(neighbor == destination)
                      break;
                }

            }
        }
            return distances[destination];
    }