Utilizzo del grafico di Boost breadth_first_search () per trovare un percorso in un grafico non ponderato e non orientato
-
22-07-2019 - |
Domanda
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!
Soluzione
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.
Altri suggerimenti
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
Devi utilizzare un albero di spanning minimo : algoritmo di ricerca. È un algoritmo avido semplice e diretto.