Weighted Graphs

We’ve already seen that graphs can come in a number of different flavors. Another useful type of graph, known as a weighted graph, adds additional information to the edges of the graph.

Here’s a weighted graph that represents a basic map of several major cities in the United States:

/books/45079/OEBPS/graphs/weighted_graph_1.png

In this graph, each edge is accompanied by a number that represents the distance in miles between the cities the edge connects. For example, there are 714 miles between Chicago and New York City.

It’s also possible to have weighted graphs that are also directional. In the following example, we can see that although a flight from Dallas to Toronto is $138, a flight from Toronto back to Dallas is $216:

/books/45079/OEBPS/graphs/weighted_graph_2.png

Weighted Graphs in Code

We need to make a slight modification to our code if we want to add weights to our graph. One way to do this is to use a hash table to represent the adjacent vertices rather than using an array:

	class WeightedGraphVertex:

	def __init__(self, value):
	self.value = value
	self.adjacent_vertices = {}

	def add_adjacent_vertex(self, vertex, weight):
	self.adjacent_vertices[vertex] = weight

As you can see, self.adjacent_vertices is now a hash table instead of an array. The hash table will contain key-value pairs, where in each pair, the adjacent vertex is the key and the weight (of the edge from this vertex to the adjacent vertex) is the value.

When we use the add_adjacent_vertex method to add an adjacent vertex, we now pass in both the adjacent vertex as well as the weight.

Since we’ll continue to deal with the example of a graph that depicts flight fares to and from various cities, we’ll create a special class called City. This is the same implementation as the preceding WeightedGraphVertex but uses class and variable names appropriate to our use case:

	class City:

	def __init__(self, name):
	self.name = name
	self.routes = {}

	def add_route(self, city, price):
	self.routes[city] = price

So if we want to create the Dallas–Toronto flight price graph from earlier, we can run the following code:

	dallas = City("Dallas")
	toronto = City("Toronto")

	dallas.add_route(toronto, 138)
	toronto.add_route(dallas, 216)

The Shortest Path Problem

Weighted graphs can be very useful in modeling all sorts of datasets, and they also come with some powerful algorithms that help us make the most out of that data.

Let’s harness one of these algorithms to save us a bit of money.

Here’s a graph that demonstrates the costs of available flights between five different cities:

/books/45079/OEBPS/graphs/weighted_graph_3.png

Now, say I’m in Atlanta and want to fly to El Paso. Unfortunately, we can see in this graph that there’s no direct route from Atlanta to El Paso at this time. However, I can get there if I’m willing to stop over in other cities along the way. For example, I can fly from Atlanta to Denver and then from Denver to El Paso. But there are other paths as well, and each path has a different price. The Atlanta--Denver--El Paso path will set me back $300, but the Atlanta--Denver–Chicago–El Paso path only costs $280.

The puzzle, now, is this: how do we create an algorithm that finds the cheapest price I’d have to shell out to get to my destination? Let’s assume we don’t care about how many stops we have to make; we’re just out to get the cheapest fare.

This kind of puzzle is known as the shortest path problem. This problem can take other forms as well. For example, if the graph showed us distances between cities, we might want to find the path that has the shortest distance. But here, the shortest path we’re looking for is the cheapest one, since the weights represent flight prices.