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

Question

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

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

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

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

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

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

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

Answer 1

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

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

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

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

Answer 2

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

1. Нет циклов

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

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

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

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

Answer 3

С учебник здесь

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

Answer 4

Я потерял 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, to, 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)

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

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

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

---

Answer 5

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

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

Answer 6

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

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();
            }
        }
}