Remember that Dijkstra’s Algorithm works like the following:
- 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 accordinglyheappop
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
At the top of the file, import heapq
.
Then, uncomment the code and run it! See what happens!