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

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