Comment fonctionne une recherche en largeur (Breadth-First Search) lorsqu'on cherche le chemin le plus court ?

Question

J'ai fait quelques recherches, et il semble qu'il me manque une petite partie de cet algorithme. Je comprends comment fonctionne la recherche en premier lieu, mais je ne comprends pas comment elle peut m'amener à un chemin spécifique, au lieu de me dire simplement où chaque nœud individuel peut aller. Je suppose que la façon la plus simple d'expliquer ma confusion est de fournir un exemple :

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

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

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

Je mets B en file d'attente et l'explore, et découvre qu'il mène à A (déjà exploré), et C, donc je mets C en file d'attente. Je mets ensuite D en file d'attente, et découvre qu'il mène à E, mon objectif. Je mets ensuite C en file d'attente, et je découvre qu'il mène également à E, mon objectif.

Je sais logiquement que le chemin le plus rapide est A->D->E, mais je ne suis pas sûr de l'utilité de la recherche en largeur - comment dois-je enregistrer les chemins de sorte que, lorsque je termine, 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 un arbre, il n'y a donc pas de nœuds "parents", seulement des enfants.

Answer 1

Sur la base de réponse d'acheron55 J'ai posté une implémentation possible ici .
En voici un bref résumé :

Tout ce que vous avez à faire, c'est de suivre le chemin par lequel la cible a été atteinte. Un moyen simple de le faire est de pousser dans le champ Queue l'ensemble du chemin utilisé pour atteindre un nœud, plutôt que le nœud lui-même.
L'avantage de cette méthode 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.

Answer 2

Une bonne explication de la façon dont BFS calcule les plus courts chemins, accompagnée de l'algorithme BFS simple le plus efficace dont j'ai connaissance et également d'un code de travail, est fournie dans l'article à comité de lecture suivant :

https://queue.acm.org/detail.cfm?id=3424304

L'article explique comment BFS calcule un arbre des plus courts chemins représenté par des pointeurs parentaux par sommet, et comment récupérer un plus court chemin particulier entre deux sommets quelconques à partir des pointeurs parentaux. L'explication de BFS prend trois formes : prose, pseudocode et un programme C fonctionnel.

L'article décrit également "Efficient BFS" (E-BFS), une variante simple du BFS classique du manuel qui améliore son efficacité. Dans l'analyse asymptotique, le temps d'exécution passe de Thêta(V+E) à Oméga(V). En d'autres termes, la BFS classique s'exécute toujours en un temps proportionnel au nombre de sommets plus le nombre d'arêtes, tandis que la E-BFS s'exécute parfois en un temps proportionnel au nombre de sommets seulement, qui peut être beaucoup plus petit. En pratique, E-BFS peut être beaucoup plus rapide, en fonction du graphe d'entrée. E-BFS n'offre parfois aucun avantage par rapport à BFS classique, mais il n'est jamais beaucoup plus lent.

Il est remarquable qu'en dépit de sa simplicité, E-BFS ne semble pas être largement connu.

Answer 3

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