What do roads, human ancestry, currency exchange, planning a wedding, and the internet have in common? They can all be represented with a mathematical object called a graph or network.

The roads and towns in this map form a graph.

The components and wiring in this electronic circuit are represented as a network.

In mathematics, the term graph refers to a diagram that consists of a set of points, called vertices, that are connected by a set of lines called edges.

Weighted edges

Networks often have numbers on the edges that give the graph meaning. For example, if we were making a network based on the roads between towns, the numbers might show the distances between towns, or how long it takes to drive from town to town.

The number on the edge is called a weight. Here is an example:

Approximate travel times, in hours, between some European capitals

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. Let's examine an approach to solving this problem which uses trial and error.

Worked example

Example 1

This network represents the roads joining five towns and the weights represent travel time in minutes. Determine the optimal (fastest) path to get from $A$A to $B$B .

Think: Determine the number of different paths we could take. Three possibilities are drawn on the network below:

Do: Calculate the time taken for each of the three options.

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.

Check that there isn't another way that is faster. The green 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, therefore ACDB is the fastest route to get from $A$A to $B$B.

Reflect: 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.

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.

Practice questions

Question 1

Find the weights of the following paths in this network:

Path $Y$Y-$E$E-$D$D:
Path $A$A-$B$B-$Z$Z-$X$X:
Path $X$X-$C$C-$A$A-$B$B-$Z$Z:

Question 2

The following map shows all possible routes in $Tobias$ 's town. $Tobias$ travels from his home to $work$ on a daily basis.

If $Tobias$ 's house is at vertex $C$C, and $work$ is at vertex $I$I, what is the shortest path between the two places?
$C,A,B,F,I$C,A,B,F,I
A
$C,E,G,J,I$C,E,G,J,I
B
$C,B,G,I$C,B,G,I
C
$E,B,F,I$E,B,F,I
D
$C,A,D,B,H,J,I$C,A,D,B,H,J,I
E
$I,F,D,A,C$I,F,D,A,C
F

Visiting each vertex

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 the shortest path that went to each house (vertex) on the delivery route.

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

Practice questions

Question 3

A private school bus is to pick up students from a certain area. The following map shows the routes connecting the students' houses.

The bus driver wants to save as much time as possible on his route. If he starts his route at vertex $D$D, what is the shortest path that visits each house exactly once?

Represent the path by listing the vertices in order, separated by commas.

Question 4

A rock band is planning a tour across several cities. The following table represents the routes and distance between the cities at which they will be performing.

Starting City	Ending City	Distance
$A$`A`	$C$`C`	$9$9
$A$`A`	$F$`F`	$6$6
$B$`B`	$E$`E`	$11$11
$B$`B`	$F$`F`	$5$5
$C$`C`	$D$`D`	$3$3
$C$`C`	$F$`F`	$7$7
$E$`E`	$D$`D`	$5$5
$E$`E`	$F$`F`	$8$8

Which of the following graphs does the table represent?
A
B
C
D
Using either the correct graph or table given, find the shortest route for the rock band to cross starting at city $A$A and passing by each city only once.

List the vertices in order, separated by commas.