Network weights
The number added to each edge is called a weight. Often it represent time, cost or distance. Here are a few examples:
Approximate travel times, in hours, between some European capitals
Average length of bonds in acetic acid ($CH_3COOH$CH3COOH), measured in Angstrom.
A simple circuit diagram, with resistances measured in Ohms.
These numbers transform the way networks are used. Weighted networks provide a lot more information, and enable more insightful analysis.
If a network has weights on its edges then a total weight is given to the whole network by adding up all the weights. This applies to subnetworks too. Similarly, a weight can be given to any walk by adding up all the weights on the edges chosen in the walk (the weight of a walk is sometimes called its length).
- This network has a weight of $4+5+7+3+6+6+11+5+16+21=84$4+5+7+3+6+6+11+5+16+21=84.
- The subnetwork in the middle (highlighted in orange) has weight $4+5+7+3+6=25$4+5+7+3+6=25.
- The red walk on the right has weight $3+5+16+11=35$3+5+16+11=35.
Practice question
Question 1
Consider the following network:
What is the weight of the edge connecting $Q$Q and $S$S?
What is the weight of the entire network?
The shortest path problem
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.
Consider this network of towns:
The weights represent travel time in minutes, what is the the optimal (fastest) path from $A$A to $B$B? The three paths that could be taken:
- The red path $AB$AB will take $9$9 minutes.
- The blue path $ACEB$ACEB $2+3+4=9$2+3+4=9 minutes.
- The green path $ADB$ADB will take $4+4=8$4+4=8 minutes.
This last path is close to the answer, but $A$A to $D$D even faster via $C$C:
This path does not look like the fastest but takes $2+1+4=7$2+1+4=7 minutes, and is the quickest way to get from $A$A to $B$B.
The same strategy can be applied to directed networks.
This time, the streets are all one-way! Try a few paths out:
The blue path $AFG$AFG takes $10+11=21$10+11=21 minutes.
The green path $ADG$ADG takes $4+12=16$4+12=16 minutes.
The purple path $ABCEG$ABCEG takes $6+1+5+5=17$6+1+5+5=17 minutes.
Now check more paths, thinking about taking detours on paths already known. Starting from the path $ADG$ADG, the best one found so far, the trip from $D$D to $G$G can be faster by going through $E$E:
The path $ADEG$ADEG only takes $4+6+5=15$4+6+5=15 minutes, and this is the fastest route.
Using trial and error is an appropriate method, however try to be systematic to ensure all paths are checked.
Practice questions
Question 2
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
DUsing 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.
Question 3
A school bus has to pick up students from a certain area. The following map shows the routes connecting the students' houses.
The school 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 for him to cross if passing over each house only once? List all vertices in order separated by a comma (e.g. $A,B,C,D$A,B,C,D)