Distance optimisation

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. We are going to learn about how they do it, and see how 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 $AB$AB takes us straight there, but it will take $9$9 minutes.
• The same is true of the blue path $ACEB$ACEB, since the weight of this path is $2+3+4=9$2+3+4=9 minutes.
• The green path $ADB$ADB 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.

We can perform the same sort of analysis on directed graphs as well:

This time, the streets are all one-way! Let’s try a few paths out:

The blue path $AFG$AFG takes $10+11=21$10+11=21 minutes.

The green path $ADG$ADG takes a little less time, at $4+12=16$4+12=16 minutes.

The purple path $ABCEG$ABCEG takes $6+1+5+5=17$6+1+5+5=17 minutes, no improvement on the green one.

We can now check more paths, thinking about taking detours on paths we already know about. Starting from the path $ADG$ADG, the best one we have found so far, we can improve the trip from $D$D to $G$G by going through $E$E:

Going along the path $ADEG$ADEG only takes $4+6+5=15$4+6+5=15 minutes, and this is the fastest route.

We will see some more sophisticated and thorough approaches in the next chapter, but this “trial-and-error” method is enough to get you started!