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.