The Self-Taught Computer Scientist

Data Structures
180
def add_vertex(self, key):
new_vertex = Vertex(key)
self.vertex_dict[key] = new_vertex
Your next method, 
get_vertex
, accepts a key as a parameter and checks 
self.vertex_dict
to see if 
the vertex is your graph.
def get_vertex(self, key):
if key in self.vertex_dict:
return self.vertex_dict[key]
return None
Finally, your graph class has a method called 
add_edge
that adds an edge between two vertices in 
your graph.
def add_edge(self, f, t, weight=0):
if f not in self.vertex_dict:
self.add_vertex(f)
if t not in self.vertex_dict:
self.add_vertex(t)
self.vertex_dict[f].add_adj(self.vertex_dict[t], weight)
Now you can create a graph and add vertices to it like this:
graph = Graph()
graph.add_vertex("A")
graph.add_vertex("B")
graph.add_vertex("C")
graph.add_edge("A", "B", 1)
graph.add_edge("B", "C", 10)
vertex_a = graph.get_vertex("A")
vertex_b = graph.get_vertex("B")
In this example, to keep things simple, two different vertices cannot have the same key.
Dijkstra’s Algorithm
When you are working with graphs, you often need to find the shortest path between two vertices. 
One of the most famous algorithms in computer science is called Dijkstra’s algorithm, and you can 
use it to find the shortest path from a vertex in a graph to every other vertex. The famous computer 
scientist Edsger Dijkstra invented it in only 20 minutes in his head without a pen or paper.
Here is how Dijkstra’s algorithm works. First, you pick a starting vertex. Your starting vertex is the 
vertex you will find the shortest path to every other vertex in your graph from. Say you have a graph 
that looks like Figure 16.11.

---

Chapter 16 Graphs
181
If A is your starting vertex, at the end of your program, you will have a dictionary that contains 
every vertex in the graph and the shortest path from the starting vertex (A) to each vertex.
{
"A": 0,
"B": 2,
"C": 6,
"D": 7,
}
As you can see from Figure 16.11, the shortest path from A to D is 7 because vertex A to vertex B 
to vertex D is 7 (2 + 5), and vertex A to vertex C to vertex D is 14 (6 + 8).
At the beginning of the algorithm, you set the path from the starting vertex to itself to zero and 
set all the other path lengths to infinity (Figure 16.12).
The key to your algorithm is a priority queue. You use a priority queue to do a breadth- first search 
through your graph. You use your priority queue to track vertices and their distances from the starting 
vertex. Let’s take a look at how this works with the graph from earlier.
Your algorithm begins with the starting vertex A in your priority queue. You keep track of all of 
the shortest paths in a dictionary. In your dictionary, you set the distance from vertex A to itself to 0 
and set all other distances to infinity (Figure 16.13). At this point, you haven’t visited any vertices 
yet. Visiting a vertex means popping it off your priority queue, and if you haven’t found a shorter path 
from the starting vertex to it, look at all the vertices adjacent to it for shorter paths to the starting 
vertex. If you find a shorter path, you put that adjacent vertex on your priority queue.
B
2
5
8
6
A
C
D