9.07 Moving through a network

In 9.01 we introduced the idea of walks and paths. Remember that a walk is a sequence of edges that moves around the network with no restrictions, whereas a path is a sequence of edges that doesn't visit any vertex twice (except if the first and last vertex are the same). If the network is simple we can represent a walk or path by a sequence of vertices.

In 9.04 we then added weights to networks and calculated the total weights of some subnetworks. We are now going to look at calculating weights of paths through a network, in order to find paths of lowest weight.

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 exactly what GPS navigation systems are built for. We are going to learn about how they do it, and see that it is not as easy as it looks!

Let’s take a look at 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:

The path $A-C-D-B$A−C−D−B 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.

 

Practice questions

Question 1

Question 2