| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2007 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Effect of new edge on shortest paths |
| Difficulty | Moderate -0.5 This is a straightforward application of Dijkstra's algorithm followed by a simple comparison of two scenarios. Part (a) is routine algorithmic execution, while part (b) requires only re-running the algorithm twice with different edges added and comparing results—no novel insight or complex problem-solving required. Slightly easier than average due to the mechanical nature of the task. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
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}
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Use Dijkstra's algorithm on Figure 1 to find the minimum time to walk from $A$ to $L$.
\item State the corresponding route.
\end{enumerate}\item 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)
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2007 Q3 [11]}}