The Self-Taught Computer Scientist

Data Structures
186
don’t care about that path because you’ve already logged a shorter path, so you use the 
continue
key-
word to jump back to the top of your 
while
loop and examine another vertex (if there is one) instead.
if current_distance > distances[current_vertex]:
continue
If the 
current_distance
is not greater than (in other words, it is shorter than or equal to) 
distances[current_vertex]
, you iterate through all of the vertices adjacent to the current vertex.
for neighbor, weight in graph[current_vertex].items():
For each adjacent vertex, you calculate its distance from the starting vertex by adding
current_ distance
to its weight. This calculation works because 
current_distance
represents how 
far from the starting vertex the current vertex is. The variable 
weight
represents how far the adjacent 
vertex is from the current vertex, so when you add them together, you get the distance from the 
starting vertex.
distance = current_distance + weight
Next, you check to see if the new path you found for that adjacent vertex is shorter than the path 
you already have for that vertex in your 
distances
dictionary. If it is, you update your dictionary with 
the new path. Then, you push the new distance and the vertex onto your priority queue so your 
algorithm can visit it.
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
When you break out of your 
while
loop, it means you’ve explored all of the vertices, and 
distances
now contains the shortest path from the starting vertex to every other vertex in your graph. All that 
is left to do now is return 
distances
.
return distances
Vocabulary
graph: An abstract data type where a piece of data connects to one or more other pieces of data.