bitwalker / bitwalker/libgraph

Incorrect A* pathfinding with undirected graph

Aperta
#11 6 commenti 0 reazioni 1 assegnatario Rivendicata da @bitwalker Vedi su GitHub
bug undirected graphs
Lingua principale
Elixir
Stelle
571
Fork
76
Metriche di merge delle PR
Nessuna PR unita negli ultimi 30g

Descrizione

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.

Guida per i contributori

Nessuna guida per i contributori indicizzata per questo repository

Valutazione

Questa issue non è ancora stata valutata.

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.