Network construction from matrix

1 Satellite navigation systems (sat navs) use a version of Dijkstra's algorithm to find the shortest route between two places. A simplified map is shown below. The values marked represent road distances, in km , for that section of road (from a place to a road junction, or between two places). \begin{figure}[h] \end{figure}

1. Use the map to construct a network with exactly 10 arcs to show the direct distances between these places, with no road junctions shown. For example, there will need to be an arc connecting \(A\) to \(B\) of weight 22, and also arcs connecting \(A\) to \(C , D\), and \(E\). There is no arc connecting \(A\) to \(F\) (because there is no route from \(A\) to \(F\) that does not pass through another place).
2. Apply Dijkstra's algorithm, starting at \(A\), to find the shortest route from \(A\) to \(F\). Dijkstra's algorithm has quadratic order (order \(n ^ { 2 }\) ).
3. If it takes 3 seconds for a certain sat nav to find the shortest route between two places when it has to process 200 places, calculate approximately how many minutes it will take when it has to process 4000 places.

4 The table defines a network in which the numbers represent lengths.

1. Draw the network.
2. Use Dijkstra's algorithm to find the shortest paths from A to each of the other vertices. Give the paths and their lengths.
3. Draw a new network containing all of the edges in your shortest paths, and find the total length of the edges in this network.
4. Find a minimum connector for the original network, draw it, and give the total length of its edges.
5. Explain why the method defined by parts (i), (ii) and (iii) does not always give a minimum connector.

1 The table defines a network in which the numbers represent lengths.

1. Draw the network.
2. Use Dijkstra's algorithm to find the shortest route from A to G . Give the route and its length.

5 A rapid transport system connects 8 stations using three railway lines.
The blue line connects A to B to C to D . The red line connects \(B\) to \(F\) to \(E\) to \(D\). The green line connects E to G to H to A .

• The travel times for the return journeys are the same as for the outward journeys (so, for example, the travel time from B to A is 5 minutes, the same as the time from A to B ).
• All travel times include time spent stopped at stations.
• No trains are delayed so the travel times are all correct.
• Give a reason why the quickest journey from A to D may take longer than 12 minutes.

3 The diagram shows a simplified map of the main streets in a small town. \includegraphics[max width=\textwidth, alt={}, center]{4db3fbc5-e664-4803-a5f2-05af376d2591-3_531_1127_301_246} Some of the junctions have traffic lights, these junctions are labelled A to F .
There are no traffic lights at junctions X and Y .
The numbers show distances, in km, between junctions. Alex needs to check that the traffic lights at junctions A to F are working correctly.

1. Find a route from A to E that has length 2.8 km . Alex has started to construct a table of shortest distances between junctions A to F. \includegraphics[max width=\textwidth, alt={}, center]{4db3fbc5-e664-4803-a5f2-05af376d2591-3_543_1173_1420_246} For example, the shortest route from C to B has length 1.7 km , the shortest route from C to D has length 2.5 km and the shortest route from C to E has length 1.8 km .
2. Complete the copy of the table in the Printed Answer Booklet.
3. Use your table from part (b) to construct a minimum spanning tree for the complete graph on the six vertices A to F .
   Beth starts from junction B and travels through every junction, including X and Y . Her route has length 5.1 km .
4. Write down the junctions in the order that Beth visited them. Do not draw on your answer from part (c).