Hacktoberfest 2026: as issues que os mantenedores marcaram para outubro, abertas e boas para iniciantes. Ver issues do Hacktoberfest

Incorrect A* pathfinding with undirected graph

Aberta
  • Algo errado?
#11 6 comentários 0 reações 1 responsável Ver no GitHub

@bitwalker já está trabalhando nisso.

Desde 2/12/2017.

Avaliação

Esta issue ainda não foi avaliada.

Descrição

bug undirected graphs

Hi there, I am just getting started with libgraph but I have noticed that I seem to be getting wrong results for the a_star function.

What I am doing basically:

g = Graph.new(type: :undirected)
|> Graph.add_edges([{:dp1, :dp2, [weight: 3]}, {:dp2, :dp3, [weight: 6]}, {:dp3, :dp4, [weight: 5]}])
|> Graph.add_edges([{:dp4, :dp5, [weight: 4]}, {:dp4, :dp6, [weight: 5]}, {:dp5, :dp6, [weight: 6]}])
|> Graph.add_edges([{:dp6, :dp7, [weight: 5]}, {:dp7, :dp8, [weight: 4]}, {:dp8, :dp9, [weight: 2]}])
|> Graph.add_edges([{:dp9, :dp10, [weight: 6]}, {:dp3, :dp5, [weight: 3]}, {:dp5, :dp1, [weight: 7]}])
|> Graph.add_edges([{:dp6, :dp3, [weight: 7]}])

iex(1)> Graph.a_star(g, :dp1, :dp6, fn v -> 0 end)

The result I get is:

[:dp1, :dp2, :dp3, :dp4, :dp6]

However, the correct result would be:

[:dp1, :dp2, :dp3, :dp6]

Thanks in advance.

PS.: If you need a picture of the graph created above just ask.

Linguagem predominante
Elixir
Estrelas
571
Forks
76
Nenhum PR com merge em 30d

Preparar o ambiente

Este projeto não oferece contêiner de desenvolvimento, Dockerfile nem guia de contribuição, então a configuração fica por sua conta: comece pelo README e veja nosso guia da primeira contribuição para os passos gerais.

Primeiros passos

  1. Leia a issue inteira e depois o guia de contribuição do projeto.
  2. Comente na issue dizendo que vai assumir — evita que duas pessoas façam o mesmo trabalho.
  3. Faça um fork do repositório e trabalhe em uma branch.
  4. Abra um pull request que referencie o número da issue.

Mais de bitwalker/libgraph

Todas as issues de bitwalker/libgraph

Issues semelhantes

Mais issues de Elixir

Receba novas issues na sua caixa de entrada

Um resumo curto de issues do GitHub para quem está começando.