Network weights
The number added to each edge is called a weight. Often it represent time 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), measured in Angstrom
A simple circuit diagram, with resistances measured in Ohms.
These numbers transform the way we look at networks. We will be able to encode a lot more information, and perform more insightful analysis.
If a network has weights on its edges, we can give a weight to the whole network by adding up all the weights. This applies to subnetworks too. Similarly, we can give a weight 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.
The subnetwork in the middle (highlighted in orange) has weight 4+5+7+3+6=25.
The red walk on the right has weight 3+5+16+11=35.
Examples
Example 1
Consider the following network:
What is the weight of the edge connecting Q and S?
What is the weight of the entire network?
The number added to each edge is called a weight.
If a network has weights on its edges, we can give a weight to the whole network by adding up all the weights. This applies to subnetworks too. Similarly, we can give a weight 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).
Shortest path problems
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.
The same strategy can be applied to directed networks.
Using trial and error is an appropriate method when solving shortest path problems. However, we need to be systematic to ensure all paths are checked.
Examples
Example 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 | C | 9 |
| A | F | 6 |
| B | E | 11 |
| B | F | 5 |
| C | D | 3 |
| C | F | 7 |
| E | D | 5 |
| E | F | 8 |
Which of the following graphs does the table represent?
Using either the correct graph or table given, find the shortest route for the rock band to cross starting at city A and passing by each city only once.
To solve shortest path problems, at each vertex, we should choose the edge with the smallest weight avoiding paths that contain extended detours from the shortest path.