Usando breadth_first_search gráfico Boost () para encontrar um caminho em um grafo não ponderada, sem direção

Question

Eu estou usando um gráfico adjacency_list, com bordas sem direção e não ponderadas. Eu preciso encontrar um caminho mais curto entre vértice u e vértice v. Devo usar breadth_first_search () a partir de u? Ao atingir v, como faço para obter o caminho, e como faço para parar a pesquisa?

Obrigado!

Answer 1

Você deve usar um dos algoritmos de menor caminho, caminho Dijkstra Shortest sendo o mais adequado, uma vez que você precisa encontrar o caminho entre apenas dois vértices. Há um exemplo por sua uso na distribuição impulso. Existem várias opções para a obtenção de saída a partir dessa função:. Quer por fornecer um mapa da propriedade distância ou construir um mapa predecessor ou escrever um visitante personalizado

Answer 2

Sim, fazer breadth_first_search () a partir de u.

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

Para encontrar o caminho mais curto, começar a partir de 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

Você precisa usar um href="http://en.wikipedia.org/wiki/Minimum_spanning_tree" rel="nofollow noreferrer"> árvore: algoritmo de busca. É um algoritmo guloso direto simples bastante.