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`.