Usando breadth_first_search gráfico Boost () para encontrar um caminho em um grafo não ponderada, sem direção
-
22-07-2019 - |
Pergunta
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!
Solução
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
Outras dicas
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
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.