Jak działa wyszukiwanie wszerz, gdy szukasz najkrótszej ścieżki?

129

Zrobiłem kilka badań i wydaje mi się, że brakuje mi jednej małej części tego algorytmu. Rozumiem, jak działa wyszukiwanie wszerz, ale nie rozumiem, jak dokładnie doprowadzi mnie do określonej ścieżki, w przeciwieństwie do zwykłego informowania mnie, gdzie może przejść każdy węzeł. Myślę, że najłatwiejszym sposobem wyjaśnienia mojego pomieszania jest podanie przykładu:

Załóżmy na przykład, że mam taki wykres:

wprowadź opis obrazu tutaj

Moim celem jest przejście od punktu A do E (wszystkie krawędzie są nieważone).

Zaczynam na A, bo to jest moje pochodzenie. Ustawiam w kolejce A, po czym natychmiast usuwam A z kolejki i eksploruję go. Daje to B i D, ponieważ A jest połączone z B i D. W ten sposób ustawiam w kolejce zarówno B, jak i D.

Wyciągam B z kolejki i badam go i stwierdzam, że prowadzi do A (już zbadanego) i C, więc ustawiam w kolejce C. Następnie usuwam D z kolejki i stwierdzam, że prowadzi to do E, mojego celu. Następnie usuwam C z kolejki i stwierdzam, że prowadzi to również do E, mojego celu.

Wiem logicznie, że najszybszą ścieżką jest A-> D-> E, ale nie jestem pewien, jak dokładnie pomaga wyszukiwanie wszerz - jak mam nagrywać ścieżki tak, że po skończeniu mogę przeanalizować wyniki i zobaczyć że najkrótszą ścieżką jest A-> D-> E?

Zauważ też, że tak naprawdę nie używam drzewa, więc nie ma węzłów „nadrzędnych”, są tylko dzieci.

Jake
źródło
2
„Zwróć też uwagę, że nie używam w rzeczywistości drzewa, więc nie ma węzłów„ nadrzędnych ”, tylko dzieci” - cóż, oczywiście będziesz musiał gdzieś przechowywać rodzica. W przypadku DFS robisz to pośrednio przez stos wywołań, w przypadku BFS musisz to zrobić jawnie. Obawiam się, że nic nie możesz z tym zrobić :)
Voo

Odpowiedzi:

85

Technicznie rzecz biorąc, samo przeszukiwanie wszerz (BFS) nie pozwala znaleźć najkrótszej ścieżki, po prostu dlatego, że BFS nie szuka najkrótszej ścieżki: BFS opisuje strategię wyszukiwania wykresu, ale nie mówi, że musisz szukać coś konkretnego.

Algorytm Dijkstry dostosowuje BFS, aby umożliwić znalezienie najkrótszych ścieżek z jednego źródła.

Aby pobrać najkrótszą ścieżkę od początku do węzła, musisz zachować dwa elementy dla każdego węzła na wykresie: jego bieżącą najkrótszą odległość i poprzedni węzeł na najkrótszej ścieżce. Początkowo wszystkie odległości są ustawione na nieskończoność, a wszystkie poprzedniki są puste. W twoim przykładzie ustawiasz odległość A na zero, a następnie kontynuujesz BFS. Na każdym kroku sprawdzasz, czy możesz poprawić odległość potomka, tj. Odległość od początku do poprzednika plus długość eksplorowanej krawędzi jest mniejsza niż aktualnie najlepsza odległość dla danego węzła. Jeśli możesz poprawić dystans, wyznacz nową najkrótszą ścieżkę i pamiętaj o poprzedniku, przez który ta ścieżka została zdobyta. Gdy kolejka BFS jest pusta, wybierz węzeł (w twoim przykładzie jest to E) i przejdź przez jego poprzedników z powrotem do początku.

Jeśli brzmi to trochę zagmatwane, wikipedia ma fajną sekcję dotyczącą pseudokodów na ten temat.

dasblinkenlight
źródło
Dziękuję Ci! Wcześniej przeczytałem pseudokod, ale nie byłem w stanie go zrozumieć, twoje wyjaśnienie sprawiło, że kliknął dla mnie
Jake,
46
Chciałbym napisać następującą notatkę dla osób, które będą patrzeć na ten post w przyszłości: Jeśli krawędzie są nieważone, nie ma potrzeby zapisywania „aktualnej najkrótszej odległości” dla każdego węzła. Wszystko, co musi być zapisane, to rodzic dla każdego wykrytego węzła. Tak więc, podczas badania węzła i umieszczania w kolejce wszystkich jego następców, po prostu ustaw rodzica tych węzłów na badany węzeł (podwoi się to jako oznaczenie ich jako „odkryte”). Jeśli ten wskaźnik nadrzędny ma wartość NUL / nil / None dla dowolnego węzła oznacza to, że nie został jeszcze wykryty przez BFS lub sam jest węzłem źródłowym / głównym.
Shashank
@Shashank Jeśli nie utrzymujemy dystansu, skąd mamy znać najkrótszą odległość, wyjaśnij więcej.
Gaurav Sehgal
12
@gauravsehgal Ten komentarz dotyczy wykresów z nieważonymi krawędziami. BFS znajdzie najkrótszą odległość po prostu ze względu na wzorzec wyszukiwania radialnego, który uwzględnia węzły w kolejności ich odległości od punktu początkowego.
Shashank
13
Wskazówka dla czytelników komentarza @ Shashank: nieważone i jednakowo ważone (np. Wszystkie krawędzie mają wagę = 5) są równoważne.
TWiStErRob
53

Jak wskazano powyżej, BFS może tylko być użyte do znalezienia najkrótszej ścieżki w wykresie, jeżeli:

  1. Nie ma pętli

  2. Wszystkie krawędzie mają taką samą wagę lub nie mają wagi.

Aby znaleźć najkrótszą ścieżkę, wszystko, co musisz zrobić, to zacząć od źródła i przeprowadzić najpierw szerokie wyszukiwanie i zatrzymać się po znalezieniu docelowego węzła. Jedyną dodatkową rzeczą, którą musisz zrobić, jest posiadanie tablicy previous [n], która będzie przechowywać poprzedni węzeł dla każdego odwiedzanego węzła. Poprzednie źródło może mieć wartość null.

Aby wydrukować ścieżkę, po prostu wykonaj pętlę przez poprzednią tablicę [] od źródła do miejsca docelowego i wydrukuj węzły. DFS można również wykorzystać do znalezienia najkrótszej ścieżki na wykresie w podobnych warunkach.

Jeśli jednak wykres jest bardziej złożony, zawiera ważone krawędzie i pętle, to potrzebujemy bardziej wyrafinowanej wersji BFS, czyli algorytmu Dijkstry.

javaProgrammer
źródło
1
Dijkstra if no -ve weights else użyj bellman ford algo if -ve
weight
Czy BFS działa, aby znaleźć wszystkie najkrótsze ścieżki między dwoma węzłami?
Maria Ines Parnisari,
35
@javaProgrammer, to nie jest w porządku. BFS można również wykorzystać do znalezienia najkrótszej ścieżki na nieważonym wykresie cyklicznym. Jeśli wykres jest nieważony, wówczas BFS można zastosować do SP, niezależnie od tego, czy występują pętle.
Andrei Kaigorodov
3
To print the path, simple loop through the previous[] array from source till you reach destination.Ale poprzednie źródło jest zerowe. Myślę, że to, co masz na myśli to, backtrace from destination using the previous array until you reach the source.
aandis
2
Dlaczego mówisz, że DFS będzie działać w podobnych warunkach? Czy nie jest możliwe, aby DFS obrał naiwną trasę okrężną, aby uzyskać od węzłów początek-> koniec, a tym samym wskazać ścieżkę, która nie jest najkrótsza?
James Wierzba
26

Z tutoriala tutaj

„Ma niezwykle przydatną właściwość, która polega na tym, że jeśli wszystkie krawędzie na wykresie są nieważone (lub mają taką samą wagę), to pierwsza wizyta węzła jest najkrótszą ścieżką do tego węzła z węzła źródłowego”

acheron55
źródło
Jest to dobre dla bezpośrednio osiągalnego węzła (1-> 2) (2 jest osiągane bezpośrednio z 1). W przypadku węzła nieosiągalnego bezpośrednio jest więcej pracy (1-> 2-> 3, 3 nie jest osiągane bezpośrednio z 1). Oczywiście nadal jest to prawdą, biorąc pod uwagę indywidualnie, tj. 1-> 2 i 2-> 3 indywidualnie to najkrótsze ścieżki.
Manohar Reddy Poreddy
11

Zmarnowałem 3 dni i
ostatecznie rozwiązałem pytanie
dotyczące wykresu używane do
znajdowania najkrótszej odległości
za pomocą BFS

Chcesz podzielić się doświadczeniem.

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

Straciłem 3 dni próbując wszystkich powyższych alternatyw, weryfikując i weryfikując ponownie i ponownie powyżej
, to nie jest problem.
(Spróbuj poświęcić czas na szukanie innych problemów, jeśli nie znajdziesz żadnych problemów z powyższymi 5).


Więcej wyjaśnień z komentarza poniżej:

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

Załóżmy, że powyżej
wykres idzie w dół
Dla A, przyległe są B i C
Dla B, przyległe to D i E
Dla C, przyległe to F i G

powiedzmy, węzeł początkowy to A

  1. kiedy dojdziesz do punktu A, do, B i C, najkrótsza odległość do B&C z punktu A wynosi 1

  2. kiedy osiągniesz D lub E, przez B, najkrótsza odległość do A i D to 2 (A-> B-> D)

podobnie A-> E to 2 (A-> B-> E)

również A-> F i A-> G wynosi 2

Więc teraz zamiast 1 odległości między węzłami, jeśli wynosi 6, po prostu pomnóż odpowiedź przez 6, na
przykład,
jeśli odległość między nimi wynosi 1, to A-> E wynosi 2 (A-> B-> E = 1 + 1 )
jeśli odległość między nimi wynosi 6, to A-> E wynosi 12 (A-> B-> E = 6 + 6)

tak, bfs mogą obrać dowolną ścieżkę,
ale obliczamy dla wszystkich ścieżek

jeśli musisz przejść od A do Z, wtedy podróżujemy wszystkimi ścieżkami od A do pośredniego I, a ponieważ będzie wiele ścieżek, odrzucamy wszystkie oprócz najkrótszej ścieżki do I, a następnie kontynuuj ponownie najkrótszą ścieżką do następnego węzła J,
jeśli istnieje wiele ścieżek od I do J, bierzemy tylko najkrótszy
przykład,
załóżmy , że
A -> I mamy odległość 5
(STEP) załóżmy, że I -> J mamy wiele ścieżek o odległości 7 i 8, ponieważ 7 jest najkrótsza
bierzemy A -> J jako 5 (A-> I najkrótsza) + 8 (teraz najkrótsza) = 13,
więc A-> J jest teraz 13
powtarzamy teraz powyżej (KROK) dla J -> K i tak dalej, aż otrzymamy do Z

Przeczytaj tę część 2 lub 3 razy i narysuj na papierze, na pewno dostaniesz to, co mówię, powodzenia


Manohar Reddy Poreddy
źródło
Czy mógłbyś wyjaśnić, w jaki sposób udało ci się znaleźć najkrótszą ścieżkę przy pierwszym wyszukiwaniu wszerz. Pierwsze przeszukiwanie wszerz polega głównie na poszukiwaniu węzła, może być n ścieżek do węzła docelowego z węzła źródłowego, a bfs mogą obrać dowolną ścieżkę. Jak określasz najlepszą ścieżkę?
przegrany
dodałem część „więcej wyjaśnień” do powyższej odpowiedzi, daj mi znać, jeśli to satysfakcjonuje
Manohar Reddy Poreddy
1
Widzę, że próbujesz uruchomić BFS na wykresie ważonym. Dystansów 7 i 8, dlaczego wybrałeś 8? dlaczego nie 7? co, jeśli węzeł 8 nie ma dalszych krawędzi do celu? Przepływ będzie musiał wtedy wybrać 7.
przegrany
dobre pytanie, zaopiniowane, tak, nie wyrzucamy, śledzimy wszystkie sąsiednie węzły, aż dotrzemy do celu. BFS będzie działać tylko wtedy, gdy istnieją tylko stałe odległości, takie jak wszystkie 7 lub wszystkie 8. Podałem ogólny, który ma 7 i 8, który jest również nazywany algorytmem Dijkstry.
Manohar Reddy Poreddy
przepraszam, nie jestem pewien, co masz na myśli, patrz en.wikipedia.org/wiki/Dijkstra's_algorithm
Manohar Reddy Poreddy
2

Na podstawie acheron55 odpowiedzi napisałem możliwą implementację tutaj .
Oto krótkie podsumowanie tego:

Jedyne, co musisz zrobić, to śledzić ścieżkę, po której osiągnięto cel. Prostym sposobem na to jest wciśnięcie Queuecałej ścieżki używanej do osiągnięcia węzła, a nie samego węzła.
Korzyścią z tego jest to, że po osiągnięciu celu kolejka zawiera ścieżkę używaną do osiągnięcia tego celu.
Ma to również zastosowanie do wykresów cyklicznych, w których węzeł może mieć więcej niż jednego rodzica.

c0der
źródło
0

Odwiedzam ten wątek po pewnym okresie bezczynności, ale biorąc pod uwagę, że nie widzę dokładnej odpowiedzi, oto moje dwa centy.

Przeszukiwanie wszerz zawsze znajdzie najkrótszą ścieżkę na nieważonym wykresie. Wykres może być cykliczny lub acykliczny.

Zobacz poniżej pseudokod. Ten pseudokod zakłada, że ​​używasz kolejki do implementacji BFS. Zakłada również, że możesz oznaczyć wierzchołki jako odwiedzone i że każdy wierzchołek przechowuje parametr odległości, który jest inicjowany do nieskończoności.

mark all vertices as unvisited
set the distance value of all vertices to infinity
set the distance value of the start vertex to 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 the value of x is the value of the end vertex: 
        return the distance value of x
    otherwise, 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
            enqueue them to the queue
if here: there is no path connecting the vertices

Zauważ, że to podejście nie działa w przypadku wykresów ważonych - zobacz algorytm Dijkstry.

Matthew Russell
źródło
-6

Poniższe rozwiązanie działa dla wszystkich przypadków testowych.

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
źródło
4
Głos za brakiem odpowiedzi na pytanie. Samo wklejenie fragmentu kodu nie zadziała na SO.
Rishabh Agrahari