11.02 Shortest paths (Extension)

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

 

Hamiltonian paths

Sometimes when finding the shortest path we have additional restrictions such as we require the path to pass through each vertex. For example, if we were planning a delivery route between several different houses, we would be looking for a path that went to each house (vertex) on the delivery route and did so in the shortest time. These types of problems are the basis of the famous travelling salesman problem, defined in the 1800s by the Irish mathematician W. R. Hamilton and by the British mathematician Thomas Kirkman.

To find solutions to such problems we look for special paths named after the mathematician W. R. Hamilton. A path that visits each vertex exactly once is called a Hamiltonian path, if the path forms a cycle then it is called a Hamiltonian cycle (or Hamiltonian circuit). A network which contains a Hamiltonian path is known as traceable. 

Here are three networks: the first has a Hamiltonian path highlighted, the second has a Hamiltonian cycle highlighted, and the third does not have a Hamiltonian path.

To solve these types of problems we will use trial and error, together with some logic.

 

Practice questions

Question 3

Question 4

Question 5