13.02 Shortest paths

Edge weights

We represent relationships in a network with edges, and often we will want to attach a measurement to each edge to show how the relationships are different. For example, if we were making a network based on the roads between towns, we might want to show the distances between towns, or how long it takes to drive, as well as, which towns are connected. 

To show this kind of extra detail, we add a number to each edge, and call this number a weight. Here is an example:

Shortest paths

A common problem posed in networks is to find the path of lowest weight between two vertices. For example, finding the best (fastest, shortest, cheapest) route between two destinations, which is what GPS navigation systems are built for. Let's examine some approaches to solving this problem.

Take for example this network of towns:

The weights represent travel time in minutes, and we want to get from $A$A to $B$B via the optimal (fastest) path. Here are three paths we could take:

• The red path $A,B$A,B takes us straight there, but it will take $9$9 minutes.
• The blue path $A,C,E,B$A,C,E,B takes the same amount of time, since the total weight of this path is $2+3+4=9$2+3+4=9 minutes.
• The green path $A,D,B$A,D,B is a little better at $4+4=8$4+4=8 minutes.

This last path is close to the answer, but we can get from $A$A to $D$D even faster if we take a shortcut through $C$C:

This path only takes $2+1+4=7$2+1+4=7 minutes, and is the fastest way to get from $A$A to $B$B. We just need to be careful and check each path, seeing if we can improve upon it by adding or removing destinations along the way.

Can you see a path that has not been listed? Can you justify not checking this path?

In theory, when trying to find the shortest path by observation we should check every path and its length. However, we can eliminate some options as possibilities by looking at the structure of the network carefully first. Firstly, recall no path will pass through the same vertex or use the same edge more than once. Also, the shortest path will not take "the long way around". For our example above the shortest path would never use the section $C,E,D$C,E,D (which take $6$6 minutes) when the path could flow directly from $C$C to $D$D in just $1$1 minute. 

We can perform the same sort of analysis on directed graphs as well, just be careful to follow the direction on the arrows when forming paths.

Using trial and error is an appropriate method, however, we need to be careful and sometimes it is difficult to ensure all paths are checked. Next lesson we we look at a different systematic approach to find the shortest path.

 

Practice questions

Question 1

Question 2