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

129

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:

entrez la description de l'image ici

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.

Jake
la source
2
"De plus, notez que j'utilise pas réellement d'arbre, donc il n'y a pas de nœuds" parents ", seulement des enfants" - eh bien, vous devrez évidemment stocker le parent quelque part. Pour DFS, vous le faites indirectement via la pile d'appels, pour BFS, vous devez le faire explicitement. Je ne crains rien de ce que vous pouvez faire :)
Voo

Réponses:

85

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.

dasblinkenlight
la source
Je vous remercie! J'avais lu le pseudocode auparavant mais je ne pouvais pas le comprendre, votre explication l'a fait cliquer pour moi
Jake
46
Je voudrais faire la note suivante pour les personnes qui regardent cet article à l'avenir: Si les bords ne sont pas pondérés, il n'est pas nécessaire de stocker la "distance la plus courte actuelle" pour chaque nœud. Tout ce qui doit être stocké est le parent de chaque nœud découvert. Ainsi, pendant que vous examinez un nœud et que vous mettez en file d'attente tous ses successeurs, définissez simplement le parent de ces nœuds sur le nœud que vous examinez (cela doublera en les marquant comme "découverts"). Si ce pointeur parent est NUL / nil / None pour un nœud donné, cela signifie soit qu'il n'a pas encore été découvert par BFS, soit il s'agit du nœud source / racine lui-même.
Shashank
@Shashank Si nous ne maintenons pas la distance, comment pourrions-nous connaître la distance la plus courte, veuillez en expliquer davantage.
Gaurav Sehgal
12
@gauravsehgal Ce commentaire concerne les graphiques avec des arêtes non pondérées. BFS trouvera la distance la plus courte simplement en raison de son modèle de recherche radiale qui considère les nœuds dans l'ordre de leur distance par rapport au point de départ.
Shashank
13
Un conseil pour les lecteurs du commentaire de @ Shashank: non pondéré et uniformément pondéré (par exemple, tous les bords ont un poids = 5) sont équivalents.
TWiStErRob
54

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.

javaProgrammer
la source
1
Dijkstra si non -ve poids sinon utiliser bellman ford algo si -ve poids
shaunak1111
BFS fonctionne-t-il pour trouver tous les chemins les plus courts entre deux nœuds?
Maria Ines Parnisari
35
@javaProgrammer, ce n'est pas juste. BFS peut également être utilisé pour trouver le chemin le plus court dans un graphique cyclique non pondéré. Si un graphique n'est pas pondéré, alors BFS peut être appliqué pour SP indépendamment du fait d'avoir des boucles.
Andrei Kaigorodov
3
To print the path, simple loop through the previous[] array from source till you reach destination.Mais le précédent de la source est nul. Je pense que ce que vous vouliez dire est backtrace from destination using the previous array until you reach the source.
aandis le
2
Pourquoi dites-vous que DFS fonctionnera dans des conditions similaires? N'est-il pas possible pour DFS de prendre une route circulaire naïve pour obtenir des nœuds début-> fin, et donc vous donner un chemin qui n'est pas le plus court?
James Wierzba
26

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"

acheron55
la source
C'est bon pour le nœud directement accessible (1-> 2) (2 est atteint directement à partir de 1). Pour un nœud non directement accessible, il y a plus de travail (1-> 2-> 3, 3 n'est pas atteint directement à partir de 1). Bien sûr, c'est toujours vrai vu individuellement, c'est-à-dire que 1-> 2 et 2-> 3 individuellement sont les chemins les plus courts.
Manohar Reddy Poreddy
11

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


Manohar Reddy Poreddy
la source
Pourriez-vous s'il vous plaît expliquer comment avez-vous réussi à trouver le chemin le plus court avec une première recherche large. Une première recherche étendue recherche principalement un nœud, il peut y avoir n chemins vers un nœud de but à partir du nœud source et bfs peut prendre n'importe quel chemin. Comment déterminez-vous le meilleur chemin?
underdog
J'ai ajouté une partie `` plus d'explications '' à la réponse ci-dessus, faites-moi savoir si cela satisfait
Manohar Reddy Poreddy
1
Je vois que vous essayez d'exécuter un BFS sur un graphique pondéré. Des distances 7 et 8 pourquoi avez-vous choisi 8? pourquoi pas 7? et si le nœud 8 n'a pas d'autres arêtes vers la destination? Le flux devra alors choisir 7.
underdog le
bonne question, voté, oui, nous ne jetons pas, nous gardons une trace de tous les nœuds adjacents, jusqu'à ce que nous atteignions destination. BFS ne fonctionnera que s'il n'y a que des distances constantes comme les 7 ou les 8. J'ai donné un générique qui a 7 et 8 qui est également appelé comme algorithme de dijkstra.
Manohar Reddy Poreddy
désolé, je ne sais pas ce que vous voulez dire, voir en.wikipedia.org/wiki/Dijkstra's_algorithm
Manohar Reddy Poreddy
2

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.

c0der
la source
0

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 (well 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.

Matthew Russell
la source
-6

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();
            }
        }
}
user3819236
la source
4
Évalué pour ne pas avoir répondu à la question. Le simple fait de coller un extrait de code ne fonctionnera pas sur SO.
Rishabh Agrahari