Incorrect A* pathfinding with undirected graph
@bitwalker y travaille déjà.
Depuis le 2/12/2017.
Évaluation
Cette issue n'a pas encore été évaluée.
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:
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.
- Langage dominant
- Elixir
- Étoiles
- 571
- Forks
- 76
- Métriques de merge des PR
- Aucune PR mergée en 30 j
Préparer son environnement
Ce projet ne fournit ni conteneur de développement, ni Dockerfile, ni guide de contribution : l'installation est à votre charge. Commencez par son README, et consultez notre guide de la première contribution pour les étapes générales.
Par où commencer
- Lisez l'issue en entier, puis le guide de contribution du projet.
- Signalez en commentaire que vous la prenez — cela évite que deux personnes fassent le même travail.
- Forkez le dépôt et travaillez sur une branche.
- Ouvrez une pull request qui référence le numéro de l'issue.
Autres issues de bitwalker/libgraph
-
Difficulté 1/5 Moins d'une heure Accessibilité débutants 35/100
-
Difficulté 4/5 3-5 jours Accessibilité débutants 35/100
-
Difficulté 4/5 3-5 jours Accessibilité débutants 35/100
-
Failing testsOuverte
Difficulté 3/5 1-2 jours Accessibilité débutants 35/100
-
Poor performance of Graph.delete_vertex/2 in large graphsPeut-être pris @stevensonmt l’a pris il y a 642 jours. Ouverte
Difficulté 5/5 Plus d'une semaine Accessibilité débutants 25/100
Toutes les issues de bitwalker/libgraph
Issues similaires
-
Difficulté 2/5 1-3 heures Accessibilité débutants 72/100
Les mainteneurs répondent en général sous 2 jours
-
ci-cd
Difficulté 2/5 1-3 heures Accessibilité débutants 72/100
carverauto/serviceradar#5648 ·
Les mainteneurs répondent en général sous 1 jour
-
enhancement
Difficulté 2/5 1-3 heures Accessibilité débutants 78/100
Les mainteneurs répondent en général sous 1 jour
-
opentelemetry_bandit: handler is detached when a client disconnects before the request starts (get_peer_data raises :enotconn)Peut-être pris @yordis l’a pris aujourd’hui. Ouverte
Difficulté 2/5 1-3 heures Accessibilité débutants 72/100
open-telemetry/opentelemetry-erlang-contrib#846 ·
Les mainteneurs répondent en général sous 1 jour
-
Difficulté 2/5 1-3 heures Accessibilité débutants 70/100