Networks

Lesson

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$`A``B`takes us straight there, but it will take $9$9 minutes. - The same is true of the
**blue path**$ACEB$`A``C``E``B`, since the weight of this path is $2+3+4=9$2+3+4=9 minutes. - The
**green path**$ADB$`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.

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$`A``F``G` takes $10+11=21$10+11=21 minutes.

The **green path** $ADG$`A``D``G` takes a little less time, at $4+12=16$4+12=16 minutes.

The **purple path** $ABCEG$`A``B``C``E``G` 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$`A``D``G`, 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$`A``D``E``G` 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!

applies network techniques to solve network problems