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

Techniquement, la recherche en premier lieu (BFS) ne vous permet pas de trouver le chemin le plus court, tout simplement parce que la BFS ne cherche pas le chemin le plus court : BFS décrit une stratégie de recherche dans un graphe, mais ne dit pas que vous devez rechercher quelque chose en particulier.

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

Afin de retrouver le plus court chemin de l'origine à un nœud, vous devez maintenir deux éléments pour chaque nœud du graphe : sa distance la plus courte actuelle et le nœud précédent dans le plus court chemin. Initialement, toutes les distances sont définies à l'infini et tous les prédécesseurs sont définis comme vides. Dans votre exemple, vous fixez la distance de A à zéro, puis vous procédez au BFS. À chaque étape, vous vérifiez si vous pouvez améliorer la distance d'un descendant, c'est-à-dire si la distance entre l'origine et le 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 plus court chemin, 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. Vous obtiendrez ainsi le chemin le plus court.

Si cela vous semble un peu confus, wikipedia a un joli section de pseudo-code sur le sujet.

Answer 2

Comme indiqué ci-dessus, BFS peut uniquement être utilisé pour trouver le plus court chemin dans un graphe 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, il suffit de partir de la source, d'effectuer une recherche en largeur et de s'arrêter lorsque vous trouvez le nœud de destination. La seule chose supplémentaire que vous devez 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 la source peut être nul.

Pour imprimer le chemin, il suffit de boucler le tableau previous[] de la source jusqu'à la destination et d'imprimer les nœuds. DFS peut également être utilisé pour trouver le plus court chemin dans un graphe dans des conditions similaires.

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

Answer 3

De tutoriel ici

"Il possède 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), alors 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."

Answer 4

J'ai perdu 3 jours
a finalement résolu une question sur les graphiques
utilisé pour
trouver la distance la plus courte
en utilisant BFS

Vous voulez 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, à vérifier et re-vérifier encore et encore ci-dessus.
ils ne sont pas le problème.
(Essayez de passer du temps à chercher d'autres problèmes, si vous n'en trouvez pas avec les 5 ci-dessus).

---

Plus d'explications du commentaire ci-dessous :

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

Supposons que le graphique ci-dessus soit le vôtre
le graphique 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 vers B & C depuis A est de 1

2. lorsque vous atteignez D ou E, en passant par B, la distance la plus courte vers A et 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, il suffit de multiplier la réponse par 6.
exemple,
si la distance entre chacun est de 1, alors A->E est de 2 (A->B->E = 1+1)
si la distance entre chaque est de 6, alors A->E est de 12 (A->B->E = 6+6)

oui, bfs peut prendre n'importe quelle voie
mais nous calculons pour tous les chemins

si vous devez aller de A à Z, alors nous parcourons tous les chemins de A à un intermédiaire I, et comme il y aura beaucoup de chemins, nous les rejetons tous sauf le plus court chemin jusqu'à I, puis nous continuons avec le plus court chemin jusqu'au prochain nœud J
encore une fois, s'il y a plusieurs chemins de I à J, nous ne prenons que le plus court
exemple,
assumer,
A -> I nous avons la distance 5
(STEP) supposons que, 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 ce qui précède (STEP) pour J -> K et ainsi de suite, jusqu'à ce que nous arrivions à Z

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

---

Answer 5

Je reviens sur ce fil de discussion après une période d'inactivité, mais étant donné que je ne vois pas de réponse approfondie, voici mes deux centimes.

La recherche en premier lieu trouvera toujours le chemin le plus court dans un graphe non pondéré. Le graphe peut être cyclique ou acyclique.

Voir ci-dessous pour le pseudocode. Ce pseudo-code suppose que vous utilisez une file d'attente pour implémenter BFS. Il 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 graphes pondérés - pour cela, voir l'algorithme de Dijkstra.