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
startvertex and a graph.
- Instantiate a
distancesdictionary that will eventually map vertices to their distance from their start vertex.
- Assign the start vertex a distance of
- Assign every other vertex a distance of
- Set up a
vertices_to_exploremin-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!
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.
distances. We’ll build out the rest of the function body between these two lines.
Above your return statement:
- Loop through each
graphand set its corresponding value within
0because the distance from the start vertex to the start vertex is
Still above the return statement, create a variable
vertices_to_explore and assign to it a list with one element inside: a tuple of
This tuple represents the
start vertex within the min-heap list.