Learn

Remember that Dijkstra’s Algorithm works like the following:

  1. Instantiate a dictionary that will eventually map vertices to their distance from their start vertex
  • Assign the start vertex a distance of 0 in a min heap
  • Assign every other vertex a distance of infinity in a min heap
  • Remove the vertex with the smallest distance from the min heap and set that to the current vertex
  • For the current vertex, consider all of it’s adjacent vertices and calculate the distance to them by (distance to the current vertex) + (edge weight of current vertex to adjacent vertex). If this new distance is less than its current distance, replace the distance.
  • Repeat 4 and 5 until the heap is empty
  • After the heap is empty, return the distances

In order to keep track of all the distances for Dijkstra’s Algorithm, we will be using a heap! Using a heap will allow removing the minimum from the heap to be efficient. In python, there is a library called heapq which we will use to do all of our dirty work for us!

The heapq method has two critical methods we will use in Dijkstra’s Algorithm: heappush and heappop.

  • heappush will add a value to the heap and adjust the heap accordingly
  • heappop will remove and return the smallest value from the heap

Let’s say we start by initializing a heap with the following tuple inside:

heap = [(0, 'A')]

We can add values to this heap like this:

heapq.heappush(heap, (1, 'B')) heapq.heappush(heap, (-4, 'C'))

We can remove the smallest value in the heap like this:

value, letter = heapq.heappop(heap)

value will be equal to -4, and letter will be equal to 'C'.

You can read more about the documentation of heapq here.

Instructions

1.

At the top of the file, import heapq.

Then, uncomment the code and run it! See what happens!

Sign up to start coding

By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.
Already have an account?