The Self-Taught Computer Scientist

Chapter 16 Graphs
185
Inside your function, you create a dictionary called 
distances
to hold the paths from the starting 
vertex to each other vertex in the graph. At the end of the algorithm, this dictionary will contain the 
shortest path from the starting vertex to every other vertex. You create the dictionary using a dictio-
nary comprehension: similar to a list comprehension but for dictionaries. Your dictionary compre-
hension maps each vertex to 
float('infinity')
: Python’s representation of infinity. You map each 
vertex to infinity because your algorithm compares the lengths of paths and the paths start as unknown, 
so you use infinity to represent that.
distances = {vertex: float('infinity') for vertex in graph}
When you pass in the dictionary (representing a graph) from earlier to 
dijkstra
, the previous code 
produces a dictionary that looks like this:
{'A': inf, 'B': inf, 'C': inf, 'D': inf}
Next, you set the distance from the starting vertex (the vertex you are finding all of the shortest paths 
from) to itself to zero since the distance between a vertex and itself is zero.
distances[starting_vertex] = 0
Next, you create a list (you will use as a priority queue) that initially holds the starting vertex and its 
distance from the starting vertex (zero):
pq = [(0, starting_vertex)]
Next comes your code to visit the vertices on your priority queue. You use a 
while
loop that runs as 
long as there is still one or more vertices left in the priority queue. You use this 
while
loop to visit all 
the vertices in your graph.
while len(pq) > 0:
Inside your 
while
loop, you pop the distance from the starting vertex and the current vertex from 
your priority queue and save them in the variables 
current_distance
and 
current_vertex
. The 
current vertex is the vertex in the priority queue that has the shortest distance from the starting vertex. 
Your priority queue automatically serves you the vertex with the shortest distance whenever you pop 
a new vertex off it (because your priority queue is a min heap).
current_distance, current_vertex = heapq.heappop(pq)
You want to process a vertex only if you haven’t already found a shorter path from that vertex to 
the starting vertex. That is why next, you check to see if the current distance from the starting vertex 
is greater than a distance you’ve already recorded in your 
distances
dictionary. If it is greater, you 

---