Uso del gráfico de Boost breadth_first_search () para encontrar una ruta en un gráfico no ponderado y no dirigido

Question

Estoy usando un gráfico adjacency_list, con bordes no dirigidos y no ponderados. Necesito encontrar el camino más corto entre el vértice u y el vértice v. ¿Debo usar breadth_first_search () a partir de u? Al llegar a v, ¿cómo obtengo la ruta y cómo detengo la búsqueda?

¡gracias!

Answer 1

Debe usar uno de los algoritmos de ruta más cortos, La ruta más corta de Dijkstra es la más adecuada, ya que necesita encontrar la ruta entre solo dos vértices. Hay un ejemplo para su uso en la distribución de impulso. Hay varias opciones para obtener resultados de esa función: ya sea proporcionando un mapa de propiedades de distancia o construyendo un mapa predecesor o escribiendo un visitante personalizado.

Answer 2

Sí, haz breadth_first_search () comenzando desde u.

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

Para encontrar la ruta más corta, comience desde 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

Debe utilizar un árbol de expansión mínima : algoritmo de búsqueda. Es un algoritmo codicioso bastante simple.