Utilisation du graphe breadth_first_search () de Boost pour rechercher un chemin dans un graphe non pondéré et non dirigé

Question

J'utilise un graphique adjacency_list, avec des arêtes non dirigées et non pondérées. Je dois trouver le chemin le plus court entre le sommet u et le sommet v. Devrais-je utiliser breadth_first_search () à partir de u? Lorsque j'atteins v, comment puis-je obtenir le chemin et comment arrêter la recherche?

merci!

Answer 1

Vous devez utiliser l'un des algorithmes de chemin le plus court, Le plus court chemin de Dijkstra est le plus approprié, car vous devez trouver le chemin entre deux sommets seulement. Il existe un exemple pour son utilisation dans la distribution boost. Il existe plusieurs options pour obtenir le résultat de cette fonction: soit en fournissant une carte de propriété de distance, soit en créant une carte prédécesseur, soit en écrivant un visiteur personnalisé.

Answer 2

Oui, effectuez breadth_first_search () à partir de u.

FOR every vertex i meet
  IF i==v: BREAK
  record predecessor of i as i.p

Pour trouver le chemin le plus court, commencez par v:

PRINT_PATH(u, v)
  IF v==u
    print u
  ELSEIF v.p==NIL
    print 'no path from u to v exists'
  ELSE PRINT_PATH(u, v.p)
    print v

Answer 3

Vous devez utiliser un arbre de recouvrement minimal :: algorithme de recherche. C'est un simple algorithme simple et glouton.