Learn

Now, let’s start writing the algorithm!

The first part of the algorithm is all about initialization! Here’s what we have to do:

  • Define the function with a start vertex and a graph.
  • Instantiate a distances dictionary that will eventually map vertices to their distance from their start vertex.
  • Assign the start vertex a distance of 0.
  • Assign every other vertex a distance of infinity.
  • Set up a vertices_to_explore min-heap list that keeps track of neighboring vertices left to explore.

After initializing these variables, we can then traverse the graph and update the distances!

Instructions

1.

Define a function dijkstras() with two parameters: graph (the graph in question) and start (the start vertex).

Inside the function body, define distances as an empty dictionary. We will keep track of all the shortest distances in this.

Return distances. We’ll build out the rest of the function body between these two lines.

2.

Above your return statement:

  • Loop through each vertex in graph and set its corresponding value within distances equal to inf.
  • Set distances[start] equal to 0 because the distance from the start vertex to the start vertex is 0.
3.

Still above the return statement, create a variable vertices_to_explore and assign to it a list with one element inside: a tuple of 0 and start.

This tuple represents the start vertex within the min-heap list.

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?