| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2011 |
| Session | January |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra with unknown edge weight |
| Difficulty | Moderate -0.3 This is a standard D1 Dijkstra's algorithm application with a straightforward follow-up about edge weights. Part (a) is routine algorithmic execution worth 6 marks. Part (b) requires understanding how a new edge affects shortest paths, but only needs comparing two specific path lengths—a typical textbook extension rather than novel problem-solving. Slightly easier than average A-level due to being algorithmic rather than requiring mathematical insight. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
The network below shows some paths on an estate. The number on each edge represents the time taken, in minutes, to walk along a path.
\begin{enumerate}[label=(\alph*)]
\item
\begin{enumerate}[label=(\roman*)]
\item Use Dijkstra's algorithm on the network to find the minimum walking time from $A$ to $J$. [6]
\item Write down the corresponding route. [1]
\end{enumerate}
\item A new subway is constructed connecting $C$ to $G$ directly. The time taken to walk along this subway is $x$ minutes. The minimum time taken to walk from $A$ to $G$ is now reduced, but the minimum time taken to walk from $A$ to $J$ is not reduced.
Find the range of possible values for $x$. [3]
\end{enumerate}
\includegraphics{figure_4}
\hfill \mbox{\textit{AQA D1 2011 Q4 [10]}}