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

131

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

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

введите описание изображения здесь

И моя цель - добраться от 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?

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

Джейк
источник
2
«Кроме того, обратите внимание, что я на самом деле использую не дерево, поэтому нет« родительских »узлов, только дочерние элементы» - ну, очевидно, вам придется где-то хранить родительский элемент. Для DFS вы делаете это косвенно через стек вызовов, для BFS вы должны делать это явно. Боюсь, вы ничего не сможете с этим поделать :)
Voo

Ответы:

85

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

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

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

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

dasblinkenlight
источник
Спасибо! Я прочитал псевдокод ранее, но не смог его понять, ваше объяснение заставило меня
задуматься
46
Я хотел бы сделать следующее замечание для людей, которые будут просматривать этот пост в будущем: если края не взвешены, нет необходимости сохранять «текущее кратчайшее расстояние» для каждого узла. Все, что нужно сохранить, - это родительский элемент для каждого обнаруженного узла. Таким образом, пока вы исследуете узел и ставите в очередь всех его преемников, просто установите родительский элемент этих узлов на узел, который вы исследуете (это будет удваиваться как пометка их «обнаруженными»). Если этот родительский указатель равен NUL / nil / None для любого данного узла это означает, что он либо еще не был обнаружен BFS, либо это сам исходный / корневой узел.
Шашанк
@Shashank Если мы не поддерживаем дистанцию, то как мы можем узнать кратчайшее расстояние, пожалуйста, объясните подробнее.
Гаурав Сегал,
12
@gauravsehgal Этот комментарий предназначен для графов с невзвешенными ребрами. BFS найдет кратчайшее расстояние просто благодаря своей схеме радиального поиска, которая рассматривает узлы в порядке их расстояния от начальной точки.
Shashank
13
Совет для читателей комментария @ Shashank: невзвешенный и равномерно взвешенный (например, все ребра имеют вес = 5) эквивалентны.
TWiStErRob
54

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

  1. Петель нет

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

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

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

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

javaProgrammer
источник
1
Dijkstra, если нет -ve весов, иначе используйте алгоритм Bellman ford, если -ve весов
shaunak1111
Работает ли BFS, чтобы найти все кратчайшие пути между двумя узлами?
Мария Инес Парнисари
35
@javaProgrammer, это неправильно. BFS также может использоваться для поиска кратчайшего пути в невзвешенном циклическом графе. Если график невзвешенный, то BFS может применяться для SP независимо от наличия петель.
Андрей Кайгородов
3
To print the path, simple loop through the previous[] array from source till you reach destination.Но предыдущее значение источника равно нулю. Я думаю , что вы имели в виду это, backtrace from destination using the previous array until you reach the source.
aandis
2
Почему вы говорите, что DFS будет работать в подобных условиях? Разве DFS не может выбрать наивный обходной маршрут от узлов start-> end и, следовательно, дать вам путь, который не является самым коротким?
Джеймс Вежба,
26

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

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

acheron55
источник
Это хорошо для напрямую достижимого узла (1-> 2) (2 достигается непосредственно из 1). Для непрямодоступного узла больше работы (1-> 2-> 3, 3 не достигается напрямую из 1). Конечно, это все еще верно, если рассматривать индивидуально, т.е. 1-> 2 и 2-> 3 по отдельности являются кратчайшими путями.
Манохар Редди Поредди
11

Я потратил 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 раза и нарисуйте на бумаге, вы обязательно поймете, о чем я говорю, удачи


Манохар Редди Поредди
источник
Не могли бы вы рассказать, как вам удалось найти кратчайший путь с помощью поиска в ширину. Поиск в ширину в основном ищет узел, может быть n путей к целевому узлу от исходного узла, и bfs может выбрать любой путь. Как вы определяете лучший путь?
андердог
Я добавил часть «дополнительных объяснений» к приведенному выше ответу, дайте мне знать, если это вас устраивает
Манохар Редди Поредди
1
Я вижу, вы пытаетесь запустить BFS на взвешенном графике. Из расстояний 7 и 8 почему вы выбрали 8? почему не 7? что, если у 8-го узла нет дальнейших ребер к месту назначения? Тогда поток должен будет выбрать 7.
андердог
хороший вопрос, проголосовали за, да, мы не выбрасываем, мы отслеживаем все соседние узлы, пока не достигнем пункта назначения. BFS будет работать только тогда, когда есть только постоянные расстояния, такие как все 7 или все 8. Я дал общий, который имеет 7 и 8, который также называется алгоритмом Дейкстры.
Manohar Reddy Poreddy
извините, не уверен, что вы имеете в виду, см. en.wikipedia.org/wiki/Dijkstra's_algorithm
Манохар Редди Поредди
2

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

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

c0der
источник
0

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

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

См. Псевдокод ниже. Этот псевдокод предполагает, что вы используете очередь для реализации 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 (well 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

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

Мэтью Рассел
источник
-7

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

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();
            }
        }
}
user3819236
источник
5
Проголосовали против, если не ответили на вопрос. Простая вставка фрагмента кода на SO не сработает.
Ришаб Аграхари