FAQ: A* Algorithm: Python - A* Python Review

This community-built FAQ covers the “A* Python Review” exercise from the lesson “A* Algorithm: Python”.

Paths and Courses
This exercise can be found in the following Codecademy content:

Computer Science

FAQs on the exercise A* Python Review

Join the Discussion. Help a fellow learner on their journey.

Ask or answer a question about this exercise by clicking reply (reply) below!

Agree with a comment or answer? Like (like) to up-vote the contribution!

Need broader help or resources? Head here.

Looking for motivation to keep learning? Join our wider discussions.

Learn more about how to use this guide.

Found a bug? Report it!

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

Hi all,
Been trying to access the “I’m ready for an extra challenge…” link above, to do an A* review. However, even though I am logged in, I keep getting blocked with a message saying “Sorry, you don’t have access to that topic!”
Has anybody else had this experience, and know how to fix it? Thanks!

How does heap pop works in A*??
When we select one vertex and starts moving in that direction after popping it, its brother sibling still remains in our heap while we continue adding other vertex as we proceed?
What if the sibling vertex that we didn’t choose gets popped of later?
I don’t understand this bit

Can someone explain please

The implementation on Codecademy might be flawed. I just came to realize this, about 8 months after doing the exercise. Growth :stuck_out_tongue:

The total distance is calculated wrongly. This happens right at the end of the code:
heappush(vertices_to_explore, (new_distance, neighbor))

The above is wrong, since the result from the heuristic calculation is included in new_distance.
In real life, we are not moving the distance between locations AND the distances between coordinates. We are only moving the distance between locations. Therefore the code should be replaced with:

heappush(vertices_to_explore, (current_distance + edge_weight, neighbor))

I have tested this and it does not break the algo. The distance traveled is greatly reduced and the traveled path remains the same. The heuristic naturally remain in the calculation happening before, since it is only after comparing the different directions that we apply the distance in the correct direction.

This is of course based on the fact that the distance is the edge weight only.

1 Like

What you say makes sense , but when I run:
a_star(manhattan_graph, thirty_sixth_and_sixth, grand_central_station)
with your fix, it tells me:
Found a path in 40 steps:…
When I run it with the original code, I get:
Found a path in 35 steps:…

There might be an issue with your suggestion in that the pathfinding no longer is an A* algorithm. I tested it out with a_star(manhattan_graph, thirty_sixth_and_sixth, grand_central_station).

When the following is included:

heappush(vertices_to_explore, (current_distance + edge_weight, neighbor))

The heap after the start station heappop is:

1 - 35th Street and 6th Avenue
1 - 37th Street and 6th Avenue
3 - 36th Street and 5th Avenue
3 - 36th Street and 7th Avenue

This means that 35th Street and 6th Avenue will be searched next. However if we use CA’s code:

heappush(vertices_to_explore, (new_distance, neighbor))

The heap after the start station heappop is:

8 - 37th Street and 6th Avenue
10 - 35th Street and 6th Avenue
10 - 36th Street and 5th Avenue
12 - 36th Street and 7th Avenue

The distance includes the heuristic distance and so 37th Street and 6th Avenue would be heappopped next which would follow an A* algorithm search pattern.

I couldn’t confirm it but your suggestion might make the code Dijkstra-esque hence why it takes 38 steps compared to CA’s which takes 35 steps.

Although you’re right in noting that paths_and_distances[target][0] == 40 which is not the actual distance of the shortest path because the value has been combined with heuristic distances along the way. It should be 12.