Utilizzo del grafico di Boost breadth_first_search () per trovare un percorso in un grafico non ponderato e non orientato

Question

Sto usando un grafico adjacency_list, con bordi non orientati e non ponderati. Devo trovare un percorso più breve tra il vertice u e il vertice v. Dovrei usare breadth_first_search () a partire da te? Quando raggiungo v, come posso ottenere il percorso e come posso interrompere la ricerca?

grazie!

Answer 1

Dovresti usare uno degli algoritmi del percorso più breve, Il percorso più breve di Dijkstra è il più adatto poiché devi trovare il percorso tra solo due vertici. Esiste un esempio per il suo utilizzo nella distribuzione boost. Esistono diverse opzioni per ottenere output da quella funzione: fornendo una mappa delle proprietà a distanza o costruendo una mappa precedente o scrivendo un visitatore personalizzato.

Answer 2

Sì, fai breadth_first_search () a partire da te.

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

Per trovare il percorso più breve, iniziare da 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

Devi utilizzare un albero di spanning minimo : algoritmo di ricerca. È un algoritmo avido semplice e diretto.