5 A network is represented by the distance matrix below. For this network a direct connection between two vertices is always shorter than an indirect connection.
| A | B | C | D | E | F | G | H |
| A | - | 130 | 100 | - | - | 250 | - | - |
| B | 130 | - | - | 50 | - | - | 170 | 100 |
| C | 100 | - | - | - | 80 | 170 | - | 90 |
| D | - | 50 | - | - | - | - | 120 | - |
| E | - | - | 80 | - | - | 140 | - | 120 |
| F | 250 | - | 170 | - | 140 | - | - | - |
| G | - | 170 | - | 120 | - | - | - | 90 |
| H | - | 100 | 90 | - | 120 | - | 90 | - |
- How does the distance matrix show that the arcs are undirected?
The shortest distance from A to E is 180 .
- Write down the shortest route from A to E .
- Use Dijkstra's algorithm on the distance matrix to find the length of the shortest route from \(\mathbf { G }\) to each of the other vertices.
The arcs represent roads and the weights represent distances in metres. The total length of all the roads is 1610 metres.
Emily and Stephen have set up a company selling ice-creams from a van.
- Emily wants to deliver leaflets to the houses along each side of each road. Find the length of the shortest continuous route that Emily can use.
- Stephen wants to drive along each road in the ice-cream van.
- Determine the length of the shortest route for Stephen if he starts at B.
- Stephen wants to use the shortest possible route.
- Find the length of the shortest possible route.
- Write down the start and end vertices of this route.