Comment fonctionne une recherche en largeur d'abord lorsque vous recherchez le chemin le plus court?

J'ai fait quelques recherches et il me semble qu'il me manque une petite partie de cet algorithme. Je comprends comment fonctionne une recherche en largeur d'abord, mais je ne comprends pas comment exactement cela me mènera à un chemin spécifique, au lieu de simplement me dire où chaque nœud individuel peut aller. Je suppose que le moyen le plus simple d'expliquer ma confusion est de donner un exemple:

Par exemple, disons que j'ai un graphique comme celui-ci:

Et mon objectif est d'aller de A à E (toutes les arêtes ne sont pas pondérées).

Je commence par A, car c'est mon origine. Je fais la queue A, puis je retire immédiatement A de la file d'attente et je l'explore. Cela donne B et D, car A est connecté à B et D.Je file donc à la fois B et D.

Je retire B de la file d'attente et l'explore, et constate que cela mène à A (déjà exploré), et C, donc je file C. Je retire alors D de la file d'attente et constate que cela mène à E, mon objectif. Je retire alors C de la file d'attente et constate que cela mène également à E, mon objectif.

Je sais logiquement que le chemin le plus rapide est A-> D-> E, mais je ne sais pas exactement comment la recherche en largeur d'abord aide - comment dois-je enregistrer des chemins de sorte que lorsque j'ai terminé, je puisse analyser les résultats et voir que le chemin le plus court est A-> D-> E?

Notez également que je n'utilise pas réellement d'arbre, donc il n'y a pas de nœuds "parents", seulement des enfants.

Techniquement, la recherche en largeur d'abord (BFS) en elle-même ne vous permet pas de trouver le chemin le plus court, simplement parce que BFS ne recherche pas le chemin le plus court: BFS décrit une stratégie pour rechercher un graphique, mais il ne dit pas que vous devez rechercher rien de particulier.

L'algorithme de Dijkstra adapte BFS pour vous permettre de trouver les chemins les plus courts à source unique.

Afin de récupérer le chemin le plus court entre l'origine et un nœud, vous devez gérer deux éléments pour chaque nœud du graphique: sa distance la plus courte actuelle et le nœud précédent dans le chemin le plus court. Au départ, toutes les distances sont définies sur l'infini et tous les prédécesseurs sont définis comme vides. Dans votre exemple, vous définissez la distance de A sur zéro, puis procédez au BFS. À chaque étape, vous vérifiez si vous pouvez améliorer la distance d'un descendant, c'est-à-dire que la distance de l'origine au prédécesseur plus la longueur de l'arête que vous explorez est inférieure à la meilleure distance actuelle pour le nœud en question. Si vous pouvez améliorer la distance, définissez le nouveau chemin le plus court et souvenez-vous du prédécesseur par lequel ce chemin a été acquis. Lorsque la file d'attente BFS est vide, choisissez un nœud (dans votre exemple, c'est E) et parcourez ses prédécesseurs jusqu'à l'origine.

Si cela semble un peu déroutant, wikipedia a une belle section de pseudocode sur le sujet.

Comme indiqué ci-dessus, BFS ne peut être utilisé pour trouver le chemin le plus court dans un graphique que si:

1. Il n'y a pas de boucles

2. Tous les bords ont le même poids ou aucun poids.

Pour trouver le chemin le plus court, tout ce que vous avez à faire est de commencer à partir de la source et d'effectuer une première recherche approfondie et de vous arrêter lorsque vous trouvez votre nœud de destination. La seule chose supplémentaire à faire est d'avoir un tableau previous [n] qui stockera le nœud précédent pour chaque nœud visité. Le précédent de source peut être nul.

Pour imprimer le chemin, parcourez simplement le tableau [] précédent depuis la source jusqu'à ce que vous atteigniez la destination et imprimez les nœuds. DFS peut également être utilisé pour trouver le chemin le plus court dans un graphique dans des conditions similaires.

Cependant, si le graphe est plus complexe, contenant des arêtes et des boucles pondérées, alors nous avons besoin d'une version plus sophistiquée de BFS, à savoir l'algorithme de Dijkstra.

Du tutoriel ici

"Il a la propriété extrêmement utile que si toutes les arêtes d'un graphe ne sont pas pondérées (ou ont le même poids), la première fois qu'un nœud est visité est le chemin le plus court vers ce nœud depuis le nœud source"

J'ai perdu 3 jours
pour résoudre une question graphique
utilisée pour
trouver la distance la plus courte en
utilisant BFS

Envie de partager l'expérience.

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

J'ai perdu 3 jours à essayer toutes les alternatives ci-dessus, en vérifiant et revérifiant encore et encore au-dessus
qu'elles ne sont pas le problème.
(Essayez de passer du temps à chercher d'autres problèmes, si vous ne trouvez pas de problèmes avec ci-dessus 5).

Plus d'explications dans le commentaire ci-dessous:

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

Supposons ci-dessus que votre graphe
va vers le bas
Pour A, les adjacents sont B & C
Pour B, les adjacents sont D & E
Pour C, les adjacents sont F & G

disons que le nœud de départ est A

1. lorsque vous atteignez A, to, B & C, la distance la plus courte entre B & C de A est 1

2. lorsque vous atteignez D ou E, via B, la distance la plus courte à A & D est 2 (A-> B-> D)

de même, A-> E est 2 (A-> B-> E)

aussi, A-> F & A-> G est 2

Donc, maintenant au lieu de 1 distance entre les nœuds, si elle est de 6, multipliez simplement la réponse par 6
exemple,
si la distance entre chacun est 1, alors A-> E est 2 (A-> B-> E = 1 + 1 )
si la distance entre chacun est 6, alors A-> E est 12 (A-> B-> E = 6 + 6)

oui, bfs peut prendre n'importe quel chemin
mais nous calculons pour tous les chemins

si vous devez aller de A à Z, alors nous parcourons tous les chemins de A à un I intermédiaire, et comme il y aura de nombreux chemins, nous rejetons tous sauf le chemin le plus court jusqu'à I, puis continuons avec le chemin le plus court jusqu'au prochain nœud J
si il y a plusieurs chemins de I à J, nous ne prenons qu'un
exemple le plus court ,
supposons,
A -> I nous avons la distance 5
(STEP) supposons, I -> J nous avons plusieurs chemins, de distances 7 & 8, puisque 7 est le plus court
nous prenons A -> J comme 5 (A-> I le plus court) + 8 (le plus court maintenant) = 13
donc A-> J est maintenant 13
nous répétons maintenant ci-dessus (STEP) pour J -> K et ainsi de suite, jusqu'à ce que nous obtenions à Z

Lisez cette partie, 2 ou 3 fois, et dessinez sur papier, vous obtiendrez sûrement ce que je dis, bonne chance

Sur la base de la réponse acheron55, j'ai publié une implémentation possible ici .
En voici un bref résumé:

Tout ce que vous avez à faire est de suivre le chemin par lequel la cible a été atteinte. Un moyen simple de le faire est de pousser dans Queuetout le chemin utilisé pour atteindre un nœud, plutôt que sur le nœud lui-même.
L'avantage de le faire est que lorsque la cible a été atteinte, la file d'attente contient le chemin utilisé pour l'atteindre.
Ceci est également applicable aux graphes cycliques, où un nœud peut avoir plus d'un parent.

Visiter ce fil après une certaine période d'inactivité, mais étant donné que je ne vois pas de réponse approfondie, voici mes deux cents.

La recherche en largeur d'abord trouvera toujours le chemin le plus court dans un graphique non pondéré. Le graphique peut être cyclique ou acyclique.

Voir ci-dessous pour le pseudocode. Ce pseudocode suppose que vous utilisez une file d'attente pour implémenter BFS. Cela suppose également que vous pouvez marquer les sommets comme visités et que chaque sommet stocke un paramètre de distance, qui est initialisé à l'infini.

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

Notez que cette approche ne fonctionne pas pour les graphiques pondérés - pour cela, voir l'algorithme de Dijkstra.

La solution suivante fonctionne pour tous les cas de test.

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