The Self-Taught Computer Scientist

Figure 16.11: A graph with four vertices
Distance:
A: 0
B: 
∞
C: 
∞
D: 
∞
Figure 16.12: Set the path to the starting vertex to zero and the other paths to infinity.

---

Data Structures
182
At this point your priority queue has only one vertex, so you pop vertex A and its distance from 
the starting vertex (0) off of your priority queue and check to see if you’ve already found a shorter 
path to this vertex. When you are looking at a new vertex from your priority queue, if you’ve already 
found a shorter path from the starting vertex to that vertex, you do not need to do anything. In this 
case, you haven’t found a shorter path to vertex A, so you iterate through all the vertices adjacent 
to vertex A.
Next, you calculate the adjacent vertices’ distances from the starting vertex. You do this by adding 
the distance you got from the priority queue to the adjacent vertex’s weight (its distance from the 
vertex you popped off your priority queue). Because your priority queue holds two pieces of information 
for each vertex on it— the vertex and its distance from the starting vertex— no matter how far you get 
away from the starting vertex, you can easily calculate the distance between a new adjacent vertex 
and the starting vertex by adding the distance you got from your priority queue to the adjacent ver-
tices’ weight.
If the adjacent vertex’s distance from the starting vertex is shorter than any of the paths you’ve 
found so far, you add the new path to your dictionary and put the adjacent vertex on your priority 
queue. In this case, you put both of the vertices adjacent to vertex A (B and C) on your priority queue 
and add their paths to your dictionary (Figure 16.14).
Now, you pop the vertex B off of your priority queue because it has the highest priority (the short-
est path to the starting vertex). You have not found a shorter path from B to the starting vertex yet, 
so you continue visiting this vertex. You check all of its adjacent vertices for shorter paths, add any 
shorter paths you find to your dictionary, and update your priority queue. In this case, B has only one 
adjacent vertex with a shorter path (D), so you update D in your dictionary to 7 and add D and its 
distance to the starting vertex to your priority queue (Figure 16.15).
Unvisited Vertices {A, B, C, D}
Priority Queue [(2, B), (6, C)]
Distances {
A: 0,
B: 2,
C: 6,
D: 
∞,
}
Figure 16.14: The data structures after visiting vertex A
Unvisited Vertices {A, B, C, D}
Priority Queue [(0, A)]
Distances {
A: 0,
B: 
∞,
C: 
∞,
D: 
∞,
}
Figure 16.13: What the data structures in your algorithm look like when it first starts

---