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
0. - Assign every other vertex a distance of
infinity. - 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!
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
vertexingraphand set its corresponding value withindistancesequal toinf. - Set
distances[start]equal to0because 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.