Learn

Let’s finish the algorithm!

First, we’ll traverse the vertices_to_explore heap until it is empty, popping off the vertex with the minimum distance from start. Inside our while loop, we’ll iterate over the neighboring vertices of current_vertex and add each neighbor (and its distance from start) to the vertices_to_explore min-heap.

In each neighbor iteration, we will do the following:

  • Identify neighbor‘s distance from start.
  • Make sure the new distance found for neighbor is less than the distance currently set for distances[neighbor].
  • Update distances[neighbor] if the new distance is smaller than the currently recorded distance.
  • Add neighbor and its distance to the vertices_to_explore min-heap.

Instructions

1.

Below where you set vertices_to_explore but before the return statement:

  • Set up a while loop that runs as long as vertices_to_explore is truthy (i.e., there are unexplored vertices remaining).
  • Inside the while loop, use multiple assignment to set current_distance and current_vertex equal to heappop(vertices_to_explore) — this will always be the vertex with the minimum distance from start.
2.

In the while loop, below where you set current_distance and current_vertex:

  • Create a for loop to iterate over each neighbor and edge_weight of current_vertex in graph.
  • In the for loop, set new_distance equal to the sum of current_distance and the edge_weight to neighbor.
3.

Still inside the for loop, create an if statement that checks if the new_distance is less than the distance recorded for that neighbor in the distances dictionary.

If so, do the following:

  • Set distances[neighbor] equal to new_distance.
  • Use heappush() to push a tuple of new_distance and neighbor onto vertices_to_explore.

Sign up to start coding

Mini Info Outline Icon
By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.

Or sign up using:

Already have an account?