7.04e Route inspection: Chinese postman, pairing odd nodes

6 The network shows a system of pipes with the lower and upper capacities for each pipe in litres per minute. \includegraphics[max width=\textwidth, alt={}, center]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-12_810_1433_429_306}

1. Find the value of the cut \(Q\).
2. Figure 3 opposite shows a partially completed diagram for a feasible flow of 24 litres per minute from \(S\) to \(T\). Indicate, on Figure 3, the flows along the edges \(B T , D E\) and \(E T\).
3. 1. Taking your answer from part (b) as an initial flow, indicate potential increases and decreases of the flow along each edge on Figure 4 opposite.
   2. Use flow augmentation on Figure 4 to find the maximum flow from \(S\) to \(T\). You should indicate any flow augmenting paths in the table and modify the potential increases and decreases of the flow on the network.
   3. Illustrate the maximum flow on Figure 5 opposite.
4. Find a cut with value equal to that of the maximum flow. You may wish to show the cut on the network above. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-13_759_1442_276_299}
   \end{figure} Figure 4 \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-13_764_1438_1930_296}
   \end{figure} \includegraphics[max width=\textwidth, alt={}, center]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-15_2349_1691_221_153} \includegraphics[max width=\textwidth, alt={}, center]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-16_2489_1719_221_150}

5 The network shows the evacuation routes along corridors in a college, from two teaching areas to the exit, in case of a fire alarm sounding. \includegraphics[max width=\textwidth, alt={}, center]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-14_729_1013_434_497} The two teaching areas are at \(A\) and \(G\) and the exit is at \(X\). The number on each edge represents the maximum number of people that can travel along a particular corridor in one minute.

1. Find the value of the cut shown on the diagram.
2. Find the maximum flow along each of the routes \(A B D X , G F B X\) and \(G H E X\) and enter their values in the table on Figure 3 opposite.
3. 1. Taking your answers to part (b) as the initial flow, use the labelling procedure on Figure 3 to find the maximum flow through the network. You should indicate any flow augmenting routes in the table and modify the potential increases and decreases of the flow on the network.
   2. State the value of the maximum flow, and, on Figure 4, illustrate a possible flow along each edge corresponding to this maximum flow.
4. During one particular fire drill, there is an obstruction allowing no more than 45 people per minute to pass through vertex \(B\). State the maximum number of people that can move through the network per minute during this fire drill. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-15_905_1559_331_292}
   \end{figure} Figure 4 \includegraphics[max width=\textwidth, alt={}, center]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-15_689_851_1370_598} Maximum flow is \(\_\_\_\_\) people per minute.

2 The network below represents a system of pipes. The number not circled on each edge represents the capacity of each pipe in litres per second. The number or letter in each circle represents an initial flow in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{5123be51-168e-4487-8cd3-33aee9e3b23f-04_1060_1076_434_466}

1. Write down the capacity of edge \(E F\).
2. State the source vertex.
3. State the sink vertex.
4. Find the values of \(x , y\) and \(z\).
5. Find the value of the initial flow.
6. Find the value of a cut through the edges \(E B , E C , E D , E F\) and \(E G\).

7 Figure 2 shows a network of pipes. Water from two reservoirs, \(R _ { 1 }\) and \(R _ { 2 }\), is used to supply three towns, \(T _ { 1 } , T _ { 2 }\) and \(T _ { 3 }\).
In Figure 2, the capacity of each pipe is given by the number not circled on each edge. The numbers in circles represent an initial flow.

1. Add a supersource, supersink and appropriate weighted edges to Figure 2. (2 marks)
2. 1. Use the initial flow and the labelling procedure on Figure 3 to find the maximum flow through the network. You should indicate any flow augmenting routes in the table and modify the potential increases and decreases of the flow on the network.
   2. State the value of the maximum flow and, on Figure 4, illustrate a possible flow along each edge corresponding to this maximum flow.
3. Confirm that you have a maximum flow by finding a cut of the same value. List the edges of your cut. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{5123be51-168e-4487-8cd3-33aee9e3b23f-18_1077_1246_1475_395}
   \end{figure} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{5123be51-168e-4487-8cd3-33aee9e3b23f-19_1049_1264_308_386}
   \end{figure} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{5123be51-168e-4487-8cd3-33aee9e3b23f-19_835_1011_1738_171}
   \end{figure}
   \includegraphics[max width=\textwidth, alt={}]{5123be51-168e-4487-8cd3-33aee9e3b23f-19_688_524_1448_1302}
   \includegraphics[max width=\textwidth, alt={}]{5123be51-168e-4487-8cd3-33aee9e3b23f-20_2256_1707_221_153}

5 [Answer this question on the insert provided.]
Fig. 1 shows a directed flow network. The weight on each arc shows the capacity in litres per second. \begin{figure}[h] \end{figure}

1. Find the capacity of the cut \(\mathscr { C }\) shown.
2. Deduce that there is no possible flow from \(S\) to \(T\) in which both arcs leading into \(T\) are saturated. Explain your reasoning clearly. Fig. 2 shows a possible flow of 160 litres per second through the network. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{09279013-7088-4db2-99dd-098b32fbcad7-05_499_1084_1471_500} \captionsetup{labelformat=empty} \caption{Fig. 2}
   \end{figure}
3. On the diagram in the insert, show the excess capacities and potential backflows for this flow.
4. Use the labelling procedure to augment the flow as much as possible. Show your working clearly, but do not obscure your answer to part (iii).
5. Show the final flow that results from part (iv). Explain clearly how you know that this flow is maximal.

Draw the complete network of shortest distances.
(ii) Starting at vertex 1, apply the nearest neighbour algorithm to the complete network of shortest distances to find a Hamilton cycle. Give the length of your cycle and interpret it in the original network.
(iii) By temporarily deleting vertex \(\mathbf { 1 }\) and its connecting arcs from the complete network of shortest distances, find a lower bound for the solution to the Travelling Salesperson's Problem in that network. Say what this implies in the original network.
(b) Solve the route inspection problem in the original network, and say how you can be sure that your solution is optimal. 4 A factory's output includes three products. To manufacture a tonne of product \(\mathrm { A } , 3\) tonnes of water are needed. Product B needs 2 tonnes of water per tonne produced, and product C needs 5 tonnes of water per tonne produced. Product A uses 5 hours of labour per tonne produced, product B uses 6 hours and product C uses 2 hours. There are 60 tonnes of water and 50 hours of labour available for tomorrow's production.

1. Formulate a linear programming problem to maximise production within the given constraints.
2. Use the simplex algorithm to solve your LP, pivoting first on your column relating to product C.
3. An extra constraint is imposed by a contract to supply at least 8 tonnes of A . Use either two stage simplex or the big M method to solve this revised problem.

3 The weights on the network represent distances. \includegraphics[max width=\textwidth, alt={}, center]{eb4e9c34-7d8f-4118-b7ec-edcd9567077f-4_451_544_324_740}

1. The answer book shows the initial tables and the results of iterations \(1,2,3\) and 5 when Floyd's algorithm is applied to the network.
   (A) Complete the two tables for iteration 4.
   (B) Use the final route table to give the shortest route from vertex \(\mathbf { 3 }\) to vertex \(\mathbf { 5 }\).
   (C) Use the final distance table to produce a complete network with weights representing the shortest distances between vertices.
2. Using the complete network of shortest distances, find a lower bound for the solution to the Travelling Salesperson Problem by deleting vertex 5 and its arcs, and by finding the length of a minimum connector for the remainder. (You may find the minimum connector by inspection.)
3. Use the nearest neighbour algorithm, starting at vertex \(\mathbf { 1 }\), to produce a Hamilton cycle in the complete network. Give the length of your cycle.
4. Interpret your Hamilton cycle in part (iii) in terms of the original network.
5. Give a walk of minimum length which traverses every arc on the original network at least once, and which returns to the start. Give the length of your walk.

\(\mathbf { 5 }\) & 4 & - & - & 2
\hline

1. Draw the complete 5-node network of shortest times. (You are not required to use an algorithm to find the shortest times.)
2. Write down the final time matrix and the final route matrix for the complete 5 -node network. (You do not need to apply Floyd's algorithm.)
3. (A) Apply the nearest neighbour algorithm to the complete 5-node network of shortest times, starting at node 1. Give the time for the cycle you produce.
   (B) Starting at node 3, a possible cycle in the complete 5-node network of shortest times is \(\mathbf { 3 2 1 5 4 3 . }\) Give the actual cycle to which this corresponds in the incomplete 5-node network of journey times.
4. By deleting node 5 and its arcs from the complete 5 -node network of shortest times, and then using Kruskal's algorithm, produce a lower bound for the solution to the associated practical travelling salesperson problem. Show clearly your use of Kruskal's algorithm.
5. In the incomplete 5-node network of journey times, find a quickest route starting at node \(\mathbf { 5 }\) and using each of the 7 arcs at least once. Give the time of your route. 4 Helen has a meeting to go to in London. She has to travel from her home in G on the south coast to KC in London. She can drive from G to the west to A to catch a train, or she can drive to the east to W to catch a train on a different line. From both A and W she can travel to mainline terminuses V or LB in London. She will then travel by tube either from V to KC , or from LB to KC . The times for the various steps of her journey are shown in the tables. Both train services and tube services are subject to occasional delays, and these are modelled in the tables.

   Driving times	to A	to W
   From G	20 min	15 min

   \multirow{2}{*}{Train journey}	To V			To LB
   	normal time	probability of delay	delay	normal time	probability of delay	delay
   From A	1 hr 40 min	0.05	10 min	1 hr 45 min	0.05	10 min
   From W	1 hr 30 min	0.10	20 min	1 hr 35 min	0.10	20 min

   \multirow{2}{*}{ Tube journey }	To KC
   \cline { 2 - 4 }	normal time	probability of delay	delay
   From V	7 min	0.20	2 min
   From LB	9 min	0.10	2 min

   Helen wants to choose the route which will give the shortest expected journey time.
6. Draw a decision tree to model Helen's decisions and the possible outcomes.
7. Calculate Helen's shortest expected journey time and give the route which corresponds to that shortest expected journey time. As she gets into her car, Helen hears a travel bulletin on the radio warning of a broken escalator at V. This means that routes through V will take Helen 10 minutes longer.
8. Find the value of the radio information, explaining your calculation.
9. Why might the shortest expected journey time not be the best criterion for choosing a route for Helen?

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. \begin{enumerate}[label=(\alph*)] \item How does the distance matrix show that the arcs are undirected? The shortest distance from A to E is 180 . \item Write down the shortest route from A to E . \item 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. \item 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. \item Stephen wants to drive along each road in the ice-cream van.

1. Determine the length of the shortest route for Stephen if he starts at B.
2. Stephen wants to use the shortest possible route.

6 A graph is shown in Fig. 1.1.
The graph is weighted to form the network represented by the weighted matrix in Fig. 1.2. The weights represent distances in km.
A dash (-) means that there is no direct arc between that pair of vertices. \begin{figure}[h] \end{figure} \begin{table}[h] \end{table} The shortest path from D to F has total weight 6.

1. Write down a path from D to F of total weight 6. The total weight of the 12 arcs in the network is 56.
2. Use the route inspection algorithm to calculate the total weight of the least weight route that covers every arc at least once, starting at vertex A.
3. Determine the total weight of the least weight route that covers every arc at least once, starting at vertex B but finishing at any vertex. Sasha wants to find a continuous route through every vertex, starting and finishing at vertex A, with the least total weight.
4. 1. Use an appropriate algorithm to find a lower bound for the total weight of Sasha's route.
   2. Use the Nearest Neighbour Algorithm, starting at vertex A, to find an upper bound for the total weight of Sasha's route. Sasha decides to use the route \(A - B - F - E - C - D - A\).
5. Comment on the suitability of this route as a solution to Sasha's problem.

4. \begin{figure}[h] \end{figure} Figure 3 represents a network of pipes in a building. The number on each arc represents the length, in metres, of the corresponding pipe.

1. Use Dijkstra's algorithm to find the shortest path from A to J . State your path and its length. On a particular day Kim needs to check each pipe. A route of minimum length, which traverses each pipe at least once and starts and finishes at A, needs to be found.
2. Use an appropriate algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear.
3. Write down a possible route, giving its length. All the pipes directly attached to B are removed. Kim needs to check all the remaining pipes and may now start at any vertex and finish at any vertex. A route is required that excludes all those pipes directly attached to B .
4. State all possible combinations of starting and finishing points so that the length of Kim's route is minimised. State the length of Kim's route.

4. \begin{figure}[h] \end{figure} [The total weight of the network is 196]
Figure 3 models a network of roads. The number on each edge gives the time, in minutes, taken to travel along that road. Oliver wishes to travel by road from A to K as quickly as possible.

1. Use Dijkstra's algorithm to find the shortest time needed to travel from A to K . State the quickest route.
   (6) On a particular day Oliver must travel from B to K via A.
2. Find a route of minimal time from B to K that includes A , and state its length.
   (2) Oliver needs to travel along each road to check that it is in good repair. He wishes to minimise the total time required to traverse the network.
3. Use the route inspection algorithm to find the shortest time needed. You must state all combinations of edges that Oliver could repeat, making your method and working clear.

5. \begin{figure}[h] \end{figure} [The total weight of the network is 106.7]
Figure 3 models a network of cycle tracks that have to be inspected. The number on each arc represents the length, in km , of the corresponding track. Angela needs to travel along each cycle track at least once and wishes to minimise the length of her inspection route. She must start and finish at A.

1. Use an appropriate algorithm to find the tracks that will need to be traversed twice. You should make your method and working clear.
2. Find a route of minimum length, starting and finishing at A . State the length of your route. A new cycle track, AC, is under construction. It will be 15 km long. Angela will have to include this new track in her inspection route.
3. State the effect this new track will have on the total length of her route. Justify your answer.

5. \begin{figure}[h] \end{figure} Figure 6 represents a network of footpaths in a park. The number on each arc is the length, in metres, of the corresponding footpath. An inspection route of minimum length that traverses each footpath at least once needs to be found.

1. Write down the nodes at which the route will start and finish.
   (1) It is now decided to start the inspection route at B and finish the inspection route at D . A route of minimum length that traverses each footpath at least once needs to be found.
2. By considering the pairings of all relevant nodes find the arcs that will need to be traversed twice. You must make your method and working clear.
3. Write down a possible shortest inspection route, giving its length.

6. \begin{figure}[h] \end{figure} [The total weight of the network is 269] Figure 3 models a network of roads. The number on each edge gives the time taken, in minutes, to travel along the corresponding road.

1. Use Dijkstra's algorithm to find the shortest time needed to travel from A to J. State the quickest route. Alan needs to travel along all the roads to check that they are in good repair. He wishes to complete his route as quickly as possible and will start at his home, H, and finish at his workplace, D.
2. By considering the pairings of all relevant nodes, find the arcs that will need to be traversed twice in Alan's inspection route from H to D. You must make your method and working clear. For Alan's inspection route from H to D
3. 1. state the number of times vertex C will appear,
   2. state the number of times vertex D will appear.
4. Determine whether it would be quicker for Alan to start and finish his inspection route at H , instead of starting at H and finishing at D . You must explain your reasoning and show all your working.

5. \begin{figure}[h] \end{figure} [The total weight of the network is 253] Figure 1 represents a network of roads between 10 cities, A, B, C, D, E, F, G, H, J and K. The number on each edge represents the length, in miles, of the corresponding road. One day, Mabintou wishes to travel from A to H. She wishes to minimise the distance she travels.

1. Use Dijkstra's algorithm to find the shortest path from A to H . State your path and its length. On another day, Mabintou wishes to travel from F to K via A.
2. Find a route of minimum length from F to K via A and state its length. The roads between the cities need to be inspected. James must travel along each road at least once. He wishes to minimise the length of his inspection route. James will start his inspection route at A and finish at J.
3. By considering the pairings of all relevant nodes, find the length of James' route. State the arcs that will need to be traversed twice. You must make your method and working clear.
   (6)
4. State the number of times that James will pass through F. It is now decided to start the inspection route at D. James must minimise the length of his route. He must travel along each road at least once but may finish at any vertex.
5. State the vertex where the new inspection route will finish.
6. Calculate the difference between the lengths of the two inspection routes.

5. \begin{figure}[h] \end{figure} [The total weight of the network is 82] \section*{Question 5 continued}

3. \begin{figure}[h] \end{figure} [The total weight of the network is 458] Figure 2 represents a network of roads between nine towns, A, B, C, D, E, F, G, H and J. The number on each edge represents the length, in kilometres, of the corresponding road.

1. 1. Use Dijkstra's algorithm to find the shortest path from A to J.
   2. State the length of the shortest path from A to J . The roads between the towns must be inspected. Claude must travel along each road at least once. Claude will start the inspection route at A and finish at J. Claude wishes to minimise the length of the inspection route.
2. By considering the pairings of all relevant nodes, find the length of Claude's route. State the arcs that will need to be traversed twice. If Claude does not start the inspection route at A and finish at J, a shorter inspection route is possible.
3. Determine the two towns at which Claude should start and finish so that the route has minimum length. Give a reason for your answer and state the length of this route.

4.

1. State three differences between Prim's algorithm and Kruskal's algorithm for finding a minimum spanning tree.
   (3) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{4609ffb5-d270-4ff3-aa44-af8442a38b66-5_864_1073_386_497} \captionsetup{labelformat=empty} \caption{Figure 4}
   \end{figure} [The total weight of the network is 341]
2. Use Prim's algorithm, starting at D , to find a minimum spanning tree for the network shown in Figure 4. You must list the arcs in the order in which you select them.
   (3) Figure 4 models a network of school corridors. The number on each arc represents the length, in metres, of that corridor. The school caretaker needs to inspect each corridor in the school to check that the fire alarms are working correctly. He wants to find a route of minimum length that traverses each corridor at least once and starts and finishes at his office, D.
3. Use the route inspection algorithm to find the corridors that will need to be traversed twice. You must make your method and working clear. The caretaker now decides to start his inspection at G. His route must still traverse each corridor at least once but he does not need to finish at G.
4. Determine the finishing point so that the length of his route is minimised. You must give reasons for your answer and state the length of his route.
   (3)
   

5. \begin{figure}[h] \end{figure} \section*{[The total weight of the network is 214]} Figure 5 models a network of canals that have to be inspected. The number on each arc represents the length, in km , of the corresponding canal. Priya needs to travel along each canal at least once and wishes to minimise the length of her inspection route. She must start and finish at A .

1. Use the route inspection algorithm to find the length of her route. State the arcs that will need to be traversed twice. You should make your method and working clear.
   (6)
2. State the number of times that vertex F would appear in Priya's route.
   (1) It is now decided to start the inspection route at H . The route must still travel along each canal at least once but may finish at any vertex.
3. Determine the finishing point so that the length of the route is minimised. You must give reasons for your answer and state the length of the minimum route.
   (3)

5. \begin{figure}[h] \end{figure}

1. Explain what is meant by the term 'path'.
   (2) Figure 4 represents a network of roads. The number on each arc represents the length, in km, of the corresponding road. Tomek wishes to travel from A to J.
2. Use Dijkstra's algorithm to find the shortest path from A to J. State your path and its length.
   (6) On a particular day, Tomek needs to travel from G to J via A.
3. Find the shortest route from G to J via A , and find its length.
   (3) The road HJ becomes damaged and cannot be used. Tomek needs to travel along all the remaining roads to check that there is no damage to any of them. The inspection route he uses must start and finish at B .
4. Use an appropriate algorithm to find the length of a shortest inspection route. State the arcs that should be repeated. You should make your method and working clear.
   (5)
5. Write down a possible shortest inspection route.
   (1)

6. \begin{figure}[h] \end{figure} \section*{[The total weight of the network is 223]} Figure 4 models a network of roads. The number on each arc represents the length, in km , of the corresponding road. Pamela wishes to travel from A to B.

1. Use Dijkstra's algorithm to find the shortest path from A to B. State your path and its length. On a particular day, Pamela must include C in her route.
2. Find the shortest route from A to B that includes C , and state its length.
   (2) Due to damage, the three roads in and out of C are closed and cannot be used. Faith needs to travel along all the remaining roads to check that there is no damage to any of them. She must travel along each of the remaining roads at least once and the length of her inspection route must be minimised. Faith will start and finish at A .
3. Use an appropriate algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear.
4. Write down a possible route, and calculate its length. You must make your calculation clear. Faith now decides to start at vertex B and finish her inspection route at a different vertex. A route of minimum length that includes each road, excluding those directly connected to C , needs to be found.
5. State the finishing vertex of Faith's route. Calculate the difference between the length of this new route and the route found in (d).

4. \begin{figure}[h] \end{figure} [The total weight of the network is 275]
Figure 5 models a network of roads between nine villages, A, B, C, D, E, F, G, H and J. The number on each edge gives the time, in minutes, to travel along the corresponding road. Mandeep wishes to travel from A to J as quickly as possible.

1. Use Dijkstra's algorithm to find the shortest time needed to travel from A to J. State the quickest route. On Monday, Mandeep must travel from D to H via A.
2. Find the shortest time needed to travel from D to H via A . State the quickest route. On Wednesday, Mandeep needs to travel along each road to check that it is in good repair. She wishes to minimise the total time required to traverse the network. Mandeep plans to start and finish her inspection route at G.
3. Use an appropriate algorithm to find the roads that need to be traversed twice. You must make your method and working clear.
4. Write down a possible route, giving its duration. On Friday, all the roads leading directly to B are closed. Mandeep needs to check all the remaining roads and may start at any village and finish at any village. A route is required that excludes all those roads leading directly to B .
5. State all possible combinations of starting and finishing points so that the duration of Mandeep's route is minimised. Calculate the duration of Mandeep's minimum route.

4. \begin{figure}[h] \end{figure} Figure 3 models a network of roads. The number on each edge gives the length, in km , of the corresponding road. The vertices, A, B, C, D, E, F and G, represent seven towns. Derek needs to visit each town. He will start and finish at A and wishes to minimise the total distance travelled.

1. By inspection, complete the two copies of the table of least distances in the answer book.
2. Starting at A, use the nearest neighbour algorithm to find an upper bound for the length of Derek's route. Write down the route that gives this upper bound.
3. Interpret the route found in (b) in terms of the towns actually visited.
4. Starting by deleting A and all of its arcs, find a lower bound for the route length. Clive needs to travel along the roads to check that they are in good repair. He wishes to minimise the total distance travelled and must start at A and finish at G .
5. By considering the pairings of all relevant nodes, find the length of Clive's route. State the edges that need to be traversed twice. You must make your method and working clear.

6. \begin{figure}[h] \end{figure} [The total weight of the network is \(383 + x\) ]
Figure 4 models a network of roads. The number on each edge gives the time, in minutes, to travel along the corresponding road. The vertices, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }\), H and J represent nine towns. Ezra wishes to travel from A to H as fast as possible. The time taken to travel between towns G and J is unknown and is denoted by \(x\) minutes. Dijkstra's algorithm is to be used to find the fastest time to travel from A to H. On Diagram 1 in the answer book the "Order of labelling" and "Final value" at A and J, and the "Working values" at J , have already been completed.

1. Use Dijkstra's algorithm to find the fastest time to travel from A to H . State the quickest route. Ezra needs to travel along each road to check it is in good repair. He wishes to minimise the total time required to traverse the network. Ezra plans to start and finish his inspection route at A . It is given that his route will take at least 440 minutes.
2. Use the route inspection algorithm and the completed Diagram 1 to find the range of possible values of \(x\).
3. Write down a possible route for Ezra. A new direct road from D to H is under construction and will take 25 minutes to travel along. Ezra will include this new road in a minimum length inspection route starting and finishing at A . It is given that this inspection route takes exactly 488 minutes.
4. Determine the value of \(x\). You must give reasons for your answer.