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
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.
Above your return statement:
- Loop through each
vertex
ingraph
and set its corresponding value withindistances
equal toinf
. - Set
distances[start]
equal to0
because the distance from the start vertex to the start vertex is0
.
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.