bitwalker / bitwalker/libgraph
Incorrect A* pathfinding with undirected graph
- Dominant language
- Elixir
- Stars
- 571
- Forks
- 76
- PR merge metrics
- No merged PRs in 30d
Description
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:
```elixir
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:
```elixir
[:dp1, :dp2, :dp3, :dp4, :dp6]
```
However, the correct result would be:
```elixir
[:dp1, :dp2, :dp3, :dp6]
```
Thanks in advance.
PS.: If you need a picture of the graph created above just ask.
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.