Como uma Pesquisa de Largura Primeira funciona ao procurar o Caminho Mais Curto?

Eu fiz algumas pesquisas e parece que falta uma pequena parte desse algoritmo. Entendo como uma Pesquisa de Largura Primeiro funciona, mas não entendo exatamente como ela me levará a um caminho específico, em vez de apenas me dizer para onde cada nó individual pode ir. Acho que a maneira mais fácil de explicar minha confusão é fornecer um exemplo:

Por exemplo, digamos que eu tenha um gráfico como este:

E meu objetivo é ir de A a E (todas as arestas não têm peso).

Começo em A, porque essa é minha origem. Enfileiro em A, seguido de desenfileirar imediatamente A e explorá-lo. Isso produz B e D, porque A está conectado a B e D. Assim, enfileiramos B e D.

Retirar a fila de B e explorá-la, e descobrir que ela leva a A (já explorada) e C, então enfileirar C. Em seguida, desenfileirar D e descobrir que isso leva a E, meu objetivo. Em seguida, retiro a fila de C e acho que isso também leva a E, meu objetivo.

Sei logicamente que o caminho mais rápido é A-> D-> E, mas não tenho certeza de como exatamente a primeira pesquisa ajuda - como devo gravar caminhos de modo que, quando terminar, possa analisar os resultados e ver que o caminho mais curto é A-> D-> E?

Além disso, observe que na verdade não estou usando uma árvore, portanto, não há nós "pais", apenas filhos.

Tecnicamente, a pesquisa por largura da primeira (BFS) por si só não permite encontrar o caminho mais curto, simplesmente porque o BFS não está procurando o caminho mais curto: o BFS descreve uma estratégia para pesquisar em um gráfico, mas não diz que você deve procurar alguma coisa em particular.

Algoritmo de Dijkstra adapta o BFS para permitir encontrar os caminhos mais curtos de fonte única.

Para recuperar o caminho mais curto da origem para um nó, é necessário manter dois itens para cada nó no gráfico: a menor distância atual e o nó anterior no caminho mais curto. Inicialmente, todas as distâncias são definidas como infinito e todos os predecessores são definidos como vazios. No seu exemplo, você define a distância de A como zero e prossegue com o BFS. Em cada etapa, você verifica se pode melhorar a distância de um descendente, ou seja, a distância da origem ao predecessor mais o comprimento da borda que você está explorando é menor que a melhor distância atual para o nó em questão. Se você puder melhorar a distância, defina o novo caminho mais curto e lembre-se do predecessor pelo qual esse caminho foi adquirido. Quando a fila BFS estiver vazia, escolha um nó (no seu exemplo, é E) e retorne seus predecessores de volta à origem.

Se isso parecer um pouco confuso, a wikipedia possui uma boa seção de pseudocódigo sobre o tópico.

Como apontado acima, o BFS pode ser usado apenas para encontrar o caminho mais curto em um gráfico se:

1. Não há loops

2. Todas as arestas têm o mesmo peso ou nenhum peso.

Para encontrar o caminho mais curto, tudo o que você precisa fazer é iniciar a partir da fonte e realizar uma primeira pesquisa abrangente e parar quando encontrar o Nó de destino. A única coisa adicional que você precisa fazer é ter uma matriz anterior [n] que armazene o nó anterior para cada nó visitado. O anterior da origem pode ser nulo.

Para imprimir o caminho, faça um loop simples através da matriz [] anterior da origem até chegar ao destino e imprimir os nós. O DFS também pode ser usado para encontrar o caminho mais curto em um gráfico em condições semelhantes.

No entanto, se o gráfico for mais complexo, contendo arestas e loops ponderados, precisamos de uma versão mais sofisticada do BFS, ou seja, o algoritmo de Dijkstra.

Do tutorial aqui

"Tem a propriedade extremamente útil de que, se todas as arestas de um gráfico não tiverem peso (ou o mesmo peso), a primeira vez que um nó for visitado é o caminho mais curto para o nó a partir do nó de origem"

Eu perdi 3 dias
finalmente resolvi uma questão gráfica
usada para
encontrar a menor distância
usando o BFS

Deseja compartilhar a experiência.

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

Perdi três dias tentando todas as alternativas acima, verificando e revendo novamente e novamente acima,
elas não são o problema.
(Tente gastar tempo procurando outros problemas, se não encontrar nenhum problema acima de 5).

Mais explicações do comentário abaixo:

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

Suponha que acima é o seu gráfico
seja descendente.
Para A, os adjacentes são B e C.
Para B, os adjacentes são D e E.
Para C, os adjacentes são F e G

digamos, o nó inicial é A

1. quando você alcança A, para, B e C, a menor distância entre B e C de A é 1

2. quando você alcança D ou E, através de B, a distância mais curta de A e D é 2 (A-> B-> D)

da mesma forma, A-> E é 2 (A-> B-> E)

também, A-> F & A-> G é 2

Portanto, agora, em vez de 1 distância entre nós, se for 6, basta multiplicar a resposta por 6
exemplo,
se a distância entre cada um for 1, então A-> E é 2 (A-> B-> E = 1 + 1 )
se a distância entre cada um é 6, então A-> E é 12 (A-> B-> E = 6 + 6)

sim, o bfs pode seguir qualquer caminho
mas estamos calculando para todos os caminhos

se você tem que ir de A a Z, então nós viajamos todos os caminhos de A a um intermediário I, e uma vez que haverá muitos caminhos que descartar tudo, mas caminho mais curto até que eu, em seguida, continuar com o caminho mais curto à frente para o próximo nó J
novamente se existem vários caminhos de I a J, tomamos apenas o menor
exemplo,
suponha,
A -> eu temos a distância 5
(STEP) assuma, I -> J temos vários caminhos, das distâncias 7 e 8, já que 7 é o menor
tomamos A -> J como 5 (A-> eu menor) + 8 (menor agora) = 13,
então A-> J é agora 13
, repetimos agora acima (STEP) para J -> K e assim por diante, até chegarmos para Z

Leia esta parte, 2 ou 3 vezes, e desenhe no papel, você certamente entenderá o que estou dizendo, boa sorte

Com base na resposta acheron55 , postei uma possível implementação aqui .
Aqui está um breve verão:

Tudo o que você precisa fazer é acompanhar o caminho pelo qual o objetivo foi alcançado. Uma maneira simples de fazer isso é entrar no Queuecaminho inteiro usado para alcançar um nó, e não no próprio nó.
O benefício de fazer isso é que, quando o destino é atingido, a fila mantém o caminho usado para alcançá-lo.
Isso também é aplicável aos gráficos cíclicos, nos quais um nó pode ter mais de um pai.

Visitando este tópico após algum período de inatividade, mas como não vejo uma resposta completa, aqui estão meus dois centavos.

A busca pela largura da primeira sempre encontrará o caminho mais curto em um gráfico não ponderado. O gráfico pode ser cíclico ou acíclico.

Veja abaixo o pseudocódigo. Esse pseudocódigo pressupõe que você esteja usando uma fila para implementar o BFS. Ele também pressupõe que você pode marcar vértices como visitados e que cada vértice armazena um parâmetro de distância, que é inicializado para o infinito.

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

Observe que essa abordagem não funciona para gráficos ponderados - para isso, consulte o algoritmo de Dijkstra.

A solução a seguir funciona para todos os casos de teste.

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