The Self-Taught Computer Scientist

Chapter 16 Graphs
183
Now you pop the vertex C off your priority queue because it has the shortest path in your priority 
queue. C is also adjacent to D, but as you saw earlier, its distance from the starting vertex is 14 and 
you’ve already found a shorter path to D, so you do not add D to your priority queue again (Figure 16.16). 
Ignoring longer paths (not visiting them again) is what makes this algorithm so efficient.
Vertex D is not adjacent to any other vertices, so once you pop off vertex D, your algorithm is 
complete (Figure 16.17).
The following is the code to implement Dijkstra’s algorithm in Python. In this case, your algorithm 
expects a graph as a dictionary of dictionaries rather than the 
Graph
class you coded earlier in the chapter.
import heapq
def dijkstra(graph, starting_vertex):
distances = {vertex: float('infinity') for vertex in graph}
distances[starting_vertex] = 0
Unvisited Vertices {A, B, C, D}
Priority Queue [(6, C) (7, D)]
Distances {
A: 0,
B: 2,
C: 6,
D: 7,
}
Figure 16.15: The data structures after visiting vertex B
Unvisited Vertices {A, B, C, D}
Priority Queue [(7, D)]
Distances {
A: 0,
B: 2,
C: 6,
D: 7,
}
Figure 16.16: The data structures after visiting vertex C
Unvisited Vertices {A, B, C, D}
Priority Queue [ ]
Distances {
A: 0,
B: 2,
C: 6,
D: 7,
}
Figure 16.17: The data structures after visiting vertex D

---

Data Structures
184
pq = [(0, starting_vertex)]
while len(pq) > 0:
current_distance, current_vertex = heapq.heappop(pq)
if current_distance > distances[current_vertex]:
continue
for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
graph = {
'A': {'B': 2, 'C': 6},
'B': {'D': 5},
'C': {'D': 8},
'D': {},
}
dijkstra(graph, 'A')
print(dijkstra(graph, 'A'))
First, you import 
heapq
because your algorithm uses a heap as a priority queue. Your function 
dijkstra
returns a dictionary containing the shortest paths from the starting vertex. Your function 
takes two parameters: a graph and the vertex you want to find the shortest paths from.
import heapq
def dijkstra(graph, starting_vertex):
In this implementation, you will pass in an adjacency list like this:
graph = {
'A': {'B': 2, 'C': 6},
'B': {'D': 5},
'C': {'D': 8},
'D': {},
}
When you call your function 
dijkstra
, you pass in the graph and a string to represent a starting 
vertex like this:
dijkstra(graph, 'A')
The starting vertex must be a vertex in the graph.

---