Как работает поиск в ширину при поиске кратчайшего пути?

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

Так, например, у меня есть такой график:

И моя цель - добраться от A до E (все ребра не взвешены).

Я начинаю с А, потому что это мое происхождение. Я ставлю A в очередь, после чего немедленно удаляю A из очереди и исследую его. Это дает B и D, потому что A соединен с B и D. Таким образом, я ставлю в очередь B и D.

Я удаляю B из очереди и исследую его, и обнаруживаю, что он ведет к A (уже исследованному) и C, поэтому я ставлю в очередь C. Затем я удаляю D из очереди и обнаруживаю, что он ведет к E, моей цели. Затем я удаляю C из очереди и обнаруживаю, что это также приводит к E, моей цели.

Я логически знаю, что самый быстрый путь - A-> D-> E, но я не уверен, как именно помогает поиск в ширину - как мне записывать пути, чтобы, когда я закончу, я могу проанализировать результаты и увидеть что кратчайший путь A-> D-> E?

Также обратите внимание, что я на самом деле не использую дерево, поэтому нет «родительских» узлов, только дочерние элементы.

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

Алгоритм Дейкстры адаптирует BFS, чтобы вы могли находить кратчайшие пути из одного источника.

Чтобы получить кратчайший путь от источника к узлу, вам необходимо поддерживать два элемента для каждого узла в графе: его текущее кратчайшее расстояние и предыдущий узел кратчайшего пути. Изначально все расстояния установлены на бесконечность, а все предшественники установлены на пустые. В вашем примере вы устанавливаете расстояние A равным нулю, а затем продолжаете работу с BFS. На каждом шаге вы проверяете, можете ли вы улучшить расстояние до потомка, то есть расстояние от начала координат до предшественника плюс длина края, который вы исследуете, меньше текущего лучшего расстояния для рассматриваемого узла. Если вы можете увеличить расстояние, установите новый кратчайший путь и запомните предшественника, через который этот путь был получен. Когда очередь BFS пуста, выберите узел (в вашем примере это E) и переместите его предшественников обратно в источник.

Если это звучит немного запутанно, в Википедии есть хороший раздел псевдокода по этой теме.

Как было отмечено выше, BFS может только быть использована , чтобы найти кратчайший путь в графе , если:

1. Петель нет

2. Все ребра имеют одинаковый вес или не имеют веса.

Чтобы найти кратчайший путь, все, что вам нужно сделать, это начать с источника и выполнить поиск в ширину, а затем остановиться, когда вы найдете целевой узел. Единственное, что вам нужно сделать, это иметь массив previous [n], который будет хранить предыдущий узел для каждого посещенного узла. Предыдущее значение источника может быть нулевым.

Чтобы распечатать путь, просто переберите массив previous [] от источника до места назначения и распечатайте узлы. DFS также может использоваться для поиска кратчайшего пути в графе в аналогичных условиях.

Однако, если граф более сложный, содержащий взвешенные ребра и петли, тогда нам понадобится более сложная версия BFS, то есть алгоритм Дейкстры.

Из учебника здесь

«У него есть чрезвычайно полезное свойство: если все ребра в графе не взвешены (или имеют одинаковый вес), то при первом посещении узла это кратчайший путь к этому узлу от исходного узла»

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

Хочу поделиться опытом.

When the (undirected for me) graph has
fixed distance (1, 6, etc.) for edges

#1
We can use BFS to find shortest path simply by traversing it
then, if required, multiply with fixed distance (1, 6, etc.)

#2
As noted above
with BFS
the very 1st time an adjacent node is reached, it is shortest path

#3
It does not matter what queue you use
   deque/queue(c++) or
   your own queue implementation (in c language)
   A circular queue is unnecessary

#4
Number of elements required for queue is N+1 at most, which I used
(dint check if N works)
here, N is V, number of vertices.

#5
Wikipedia BFS will work, and is sufficient.
    https://en.wikipedia.org/wiki/Breadth-first_search#Pseudocode

Я потерял 3 дня, пробуя все вышеперечисленные альтернативы, проверяя и повторно проверяя снова и снова, выше
они не являются проблемой.
(Попробуйте потратить время на поиск других проблем, если вы не нашли проблем с выше 5).

Дополнительное объяснение из комментария ниже:

      A
     /  \
  B       C
 /\       /\
D  E     F  G

Предположим, что выше ваш граф-
график идет вниз.
Для A, смежные - B и C.
Для B, смежные - D и E.
Для C, смежные - F и G.

скажем, начальным узлом является A

1. когда вы достигнете A, до, B и C, кратчайшее расстояние до B и C от A равно 1

2. когда вы достигнете D или E, через B, кратчайшее расстояние до A и D равно 2 (A-> B-> D)

аналогично, A-> E равно 2 (A-> B-> E)

кроме того, A-> F & A-> G равно 2

Итак, теперь вместо 1 расстояния между узлами, если оно равно 6, просто умножьте ответ на 6
примеров,
если расстояние между каждым из них равно 1, тогда A-> E равно 2 (A-> B-> E = 1 + 1 )
если расстояние между ними равно 6, то A-> E равно 12 (A-> B-> E = 6 + 6)

да, бойцы могут пойти по любому пути
но мы рассчитываем для всех путей

если вам нужно пройти от A до Z, тогда мы проходим все пути от A до промежуточного I, и, поскольку будет много путей, мы отбрасываем все, кроме кратчайшего пути до I, а затем продолжаем кратчайший путь до следующего узла J
снова, если есть несколько путей от I до J, мы берем только один самый короткий
пример,
предположим,
A -> I у нас есть расстояние 5
(ШАГ) предположим, I -> J у нас есть несколько путей с расстояниями 7 и 8, поскольку 7 является самым коротким
мы берем A -> J как 5 (A-> I самое короткое) + 8 (самое короткое сейчас) = 13,
так что A-> J теперь 13,
мы повторяем теперь выше (STEP) для J -> K и так далее, пока не получим к Z

Прочтите эту часть 2 или 3 раза и нарисуйте на бумаге, вы обязательно поймете, о чем я говорю, удачи

На основе acheron55 ответ я отправил возможную реализацию здесь .
Вот его краткое изложение:

Все, что вам нужно сделать, это отслеживать путь, по которому была достигнута цель. Простой способ сделать это - протолкнуть Queueвесь путь, используемый для достижения узла, а не сам узел.
Преимущество этого заключается в том, что, когда цель достигнута, очередь содержит путь, используемый для ее достижения.
Это также применимо к циклическим графам, где у узла может быть более одного родителя.

Посещение этой ветки после некоторого периода бездействия, но с учетом того, что я не вижу подробного ответа, вот мои два цента.

Поиск в ширину всегда находит кратчайший путь в невзвешенном графе. График может быть циклическим или ациклическим.

См. Псевдокод ниже. Этот псевдокод предполагает, что вы используете очередь для реализации BFS. Также предполагается, что вы можете пометить вершины как посещенные, и что каждая вершина хранит параметр расстояния, который инициализируется как бесконечность.

mark all vertices as unvisited
set the distance value of all vertices to infinity
set the distance value of the start vertex to 0
if the start vertex is the end vertex, return 0
push the start vertex on the queue
while(queue is not empty)   
    dequeue one vertex (we’ll call it x) off of the queue
    if x is not marked as visited:
        mark it as visited
        for all of the unmarked children of x:
            set their distance values to be the distance of x + 1
            if the value of x is the value of the end vertex: 
                return the distance of x
            otherwise enqueue it to the queue
if here: there is no path connecting the vertices

Обратите внимание, что этот подход не работает для взвешенных графов - для этого см. Алгоритм Дейкстры.

Следующее решение работает для всех тестовых случаев.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

   public static void main(String[] args)
        {
            Scanner sc = new Scanner(System.in);

            int testCases = sc.nextInt();

            for (int i = 0; i < testCases; i++)
            {
                int totalNodes = sc.nextInt();
                int totalEdges = sc.nextInt();

                Map<Integer, List<Integer>> adjacencyList = new HashMap<Integer, List<Integer>>();

                for (int j = 0; j < totalEdges; j++)
                {
                    int src = sc.nextInt();
                    int dest = sc.nextInt();

                    if (adjacencyList.get(src) == null)
                    {
                        List<Integer> neighbours = new ArrayList<Integer>();
                        neighbours.add(dest);
                        adjacencyList.put(src, neighbours);
                    } else
                    {
                        List<Integer> neighbours = adjacencyList.get(src);
                        neighbours.add(dest);
                        adjacencyList.put(src, neighbours);
                    }


                    if (adjacencyList.get(dest) == null)
                    {
                        List<Integer> neighbours = new ArrayList<Integer>();
                        neighbours.add(src);
                        adjacencyList.put(dest, neighbours);
                    } else
                    {
                        List<Integer> neighbours = adjacencyList.get(dest);
                        neighbours.add(src);
                        adjacencyList.put(dest, neighbours);
                    }
                }

                int start = sc.nextInt();

                Queue<Integer> queue = new LinkedList<>();

                queue.add(start);

                int[] costs = new int[totalNodes + 1];

                Arrays.fill(costs, 0);

                costs[start] = 0;

                Map<String, Integer> visited = new HashMap<String, Integer>();

                while (!queue.isEmpty())
                {
                    int node = queue.remove();

                    if(visited.get(node +"") != null)
                    {
                        continue;
                    }

                    visited.put(node + "", 1);

                    int nodeCost = costs[node];

                    List<Integer> children = adjacencyList.get(node);

                    if (children != null)
                    {
                        for (Integer child : children)
                        {
                            int total = nodeCost + 6;
                            String key = child + "";

                            if (visited.get(key) == null)
                            {
                                queue.add(child);

                                if (costs[child] == 0)
                                {
                                    costs[child] = total;
                                } else if (costs[child] > total)
                                {
                                    costs[child] = total;
                                }
                            }
                        }
                    }
                }

                for (int k = 1; k <= totalNodes; k++)
                {
                    if (k == start)
                    {
                        continue;
                    }

                    System.out.print(costs[k] == 0 ? -1 : costs[k]);
                    System.out.print(" ");
                }
                System.out.println();
            }
        }
}