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

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:

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.

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.

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.

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”

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

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.

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 (we’ll 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.

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