Effect of new edge on shortest paths

6 [Figure 1, printed on a separate sheet, is provided for use in this question.]
A theme park is built on two levels. The levels are connected by a staircase. There are five rides on each of the levels. The diagram shows the ten rides: \(A , B , \ldots \ldots J\). The numbers on the edges represent the times, in minutes, taken to travel between pairs of rides. \includegraphics[max width=\textwidth, alt={}, center]{76bccb26-f2ec-4798-bb6b-89c922f9651a-05_984_1593_584_226}

1. Use Dijkstra's algorithm on Figure 1 to find the minimum time to travel from \(A\) to \(J\).
2. A new staircase is built connecting rides \(B\) and \(G\). The time taken to travel from \(B\) to \(G\) using this staircase is \(x\) minutes, where \(x\) is an integer. The time taken to travel from \(A\) to \(G\) is reduced, but the time taken to travel from \(A\) to \(J\) is not reduced. Find two inequalities for \(x\) and hence state the value of \(x\).
   (4 marks)

6 The network below shows the lengths of roads, in miles, connecting 10 towns, \(A , B , \ldots , J\).

1. Use Dijkstra's algorithm on the network to find the shortest distance from \(A\) to \(J\). Show all your working at each vertex.
2. Write down the corresponding route.
3. A new road is to be constructed connecting \(B\) to \(G\). Find the length of this new road if the shortest distance from \(A\) to \(J\) is reduced by 10 miles. State the new route.
   (3 marks) \includegraphics[max width=\textwidth, alt={}, center]{5a414265-6273-41c5-ad5f-f6316bd774d0-12_1846_1719_861_150}

3 [Figure 1, printed on the insert, is provided for use in this question.]
The following network represents the footpaths connecting 12 buildings on a university campus. The number on each edge represents the time taken, in minutes, to walk along a footpath. \includegraphics[max width=\textwidth, alt={}, center]{eb305e75-0e85-4f99-8f04-27046a153532-03_899_1317_589_356}

1. 1. Use Dijkstra's algorithm on Figure 1 to find the minimum time to walk from \(A\) to \(L\).
   2. State the corresponding route.
2. A new footpath is to be constructed. There are two possibilities:
   from \(A\) to \(D\), with a walking time of 30 minutes; or from \(A\) to \(I\), with a walking time of 20 minutes. Determine which of the two alternative new footpaths would reduce the walking time from \(A\) to \(L\) by the greater amount.
   (3 marks)

5 A fair comes to town one year and sets up its rides in two large fields that are separated by a river. The diagram shows the ten main rides, at \(A , B , C , \ldots , J\). The numbers on the edges represent the times, in minutes, it takes to walk between pairs of rides. A footbridge connects the rides at \(D\) and \(F\).

1. 1. Use Dijkstra's algorithm on the diagram below to find the minimum time to walk from \(A\) to each of the other main rides.
   2. Write down the route corresponding to the minimum time to walk from \(A\) to \(G\).
2. The following year, the fair returns. In addition to the information shown on the diagram, another footbridge has been built to connect the rides at \(E\) and \(G\). This reduces the time taken to travel from \(A\) to \(G\), but the time taken to travel from \(A\) to \(J\) is not reduced. The time to walk across the footbridge from \(E\) to \(G\) is \(x\) minutes, where \(x\) is an integer. Find two inequalities for \(x\) and hence state the value of \(x\). \section*{Answer space for question 5}
   1. (i) \includegraphics[max width=\textwidth, alt={}, center]{fb95068f-f76d-492a-b385-bce17b26ae30-12_659_1591_1692_223}