Shortest Path Problems

In this chapter, we’ll focus on algorithms that can compute shortest paths in weighted graphs. We already saw in the previous chapter that shortest paths in unweighted graphs can be computed using a simple Breadth-First Search algorithm. But the most interesting real-life shortest path problems will require us to use weighted graphs to model the problem domain.

Navigating a city

We’ll start with the classical example of a shortest path problem: navigation. Let’s say that we are located in London at Piccadilly Circus and want to get to Liverpool Street as quickly as possible, using the London Tube (the city’s subway network).

We can model this as a graph problem where the nodes are different subway stations and the edges correspond to the subway lines running between them. We can take the physical distance between two stations in miles as the weight of each edge. All transportation lines run both ways, so the graph is undirected.

Because the London subway network is notoriously complex, we’ll have reduced the number of available stations and connections for the sake of the example. In the graph above, the shortest path from the node labeled Piccadilly Circus to the node labeled Liverpool Street is

Piccadilly Circus -> Embankment -> Liverpool Street

and has a length of $0.7 + 2 = 2.7$. The path corresponds to the real-life shortest path from Piccadilly Circus to Liverpool Street along the given transport lines, which has a length of 2.7 miles.

In reality, we might not be interested in minimizing the actual distance of the connection, but rather the time spent commuting. To solve this related problem, we can use the graph with the same nodes and edges. The only required change is to take the travel times in minutes along each route as the weight of each edge. A shortest path in this graph will then ...