| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2012 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Basic Dijkstra's algorithm application |
| Difficulty | Easy -1.2 This is a straightforward application of Dijkstra's algorithm, a standard D1 topic requiring only mechanical execution of the algorithm on a given network, followed by a simple speed-distance-time calculation. No problem-solving insight or novel approach is needed—just routine procedural work. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
## Question 4
(a) (i) Use Dijkstra's algorithm on the network to find the shortest possible driving time from A to J. (5 marks)
- M1: Initial labelling of vertex A
- M1: Correct application of Dijkstra's algorithm with systematic labelling
- M1: Working values shown for at least three iterations
- M1: Final shortest distance to J correctly identified
- A1: Correct shortest time stated
(ii) Write down the corresponding route. (1 mark)
- A1: Correct route identified from algorithm
(b) A new ring road is to be constructed connecting A to J directly. Find the maximum length of this new road from A to J if the time taken to drive along it, travelling at an average speed of 90 km/h, is to be no more than the time found in part (a)(i). (2 marks)
- M1: Correct use of time from part (a)(i) with speed conversion
- A1: Maximum length correctly calculated4 The edges on the network below represent some major roads in a city. The number on each edge is the minimum time taken, in minutes, to drive along that road.
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Use Dijkstra's algorithm on the network to find the shortest possible driving time from $A$ to $J$.
\item Write down the corresponding route.
\end{enumerate}\item A new ring road is to be constructed connecting $A$ to $J$ directly.
Find the maximum length of this new road from $A$ to $J$ if the time taken to drive along it, travelling at an average speed of $90 \mathrm {~km} / \mathrm { h }$, is to be no more than the time found in part (a)(i).
\section*{(a)(i)}
\includegraphics[max width=\textwidth, alt={}, center]{1258a6d3-558a-46dc-a916-d71f71b175ff-08_912_1276_1053_429}
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2012 Q4 [8]}}