bitwalker / bitwalker/libgraph

Incorrect A* pathfinding with undirected graph

Open
#11 6 comments 0 reactions 1 assignee Claimed by @bitwalker View on GitHub
bug undirected graphs
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.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.