| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2011 |
| Session | June |
| Marks | 9 |
| 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 small network with clearly labeled vertices and edges. Part (b) requires reading values already computed in part (a), making it even more routine. No problem-solving insight or novel approach is needed. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Correct order of labelling nodes | M1 | Must show working values at each node |
| \(O = 0\) | B1 | Starting node |
| \(F = [7], S = [10], M = [6]\) (working values from O) | M1 | Correct temporary labels from O |
| \(T = [8], M\) permanent \(= 6\) | A1 | Correct permanent labels in correct order |
| \(S\) permanent \(= 10\), \(R = [9]\), \(T\) permanent \(= 8\) | A1 | |
| \(E = [12]\), \(R\) permanent \(= 9\), \(B = [12]\) | A1 | |
| \(D = [26]\) via \(E\), or correct permanent label for \(D = 26\) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(O \to M \to R \to B \to D\) | B1 | Follow through from (a)(i) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(12\) minutes | B1 | From Dijkstra's working in (a)(i) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(O \to M \to R \to B\) | B1 | Follow through from (a)(i) |
# Question 4:
## Part (a)(i) - Dijkstra's Algorithm (O to D)
| Answer | Mark | Guidance |
|--------|------|----------|
| Correct order of labelling nodes | M1 | Must show working values at each node |
| $O = 0$ | B1 | Starting node |
| $F = [7], S = [10], M = [6]$ (working values from O) | M1 | Correct temporary labels from O |
| $T = [8], M$ permanent $= 6$ | A1 | Correct permanent labels in correct order |
| $S$ permanent $= 10$, $R = [9]$, $T$ permanent $= 8$ | A1 | |
| $E = [12]$, $R$ permanent $= 9$, $B = [12]$ | A1 | |
| $D = [26]$ via $E$, or correct permanent label for $D = 26$ | A1 | |
## Part (a)(ii) - Route O to D
| Answer | Mark | Guidance |
|--------|------|----------|
| $O \to M \to R \to B \to D$ | B1 | Follow through from (a)(i) |
## Part (b)(i) - Minimum walking time O to B
| Answer | Mark | Guidance |
|--------|------|----------|
| $12$ minutes | B1 | From Dijkstra's working in (a)(i) |
## Part (b)(ii) - Route O to B
| Answer | Mark | Guidance |
|--------|------|----------|
| $O \to M \to R \to B$ | B1 | Follow through from (a)(i) |
---4 The network below shows some pathways at a school connecting different departments. The number on each edge represents the time taken, in minutes, to walk along that pathway.
Carol, the headteacher, wishes to walk from her office ( $O$ ) to the Drama department (D) .
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Use Dijkstra's algorithm on the network to find the minimum walking time from $O$ to $D$.
\item Write down the corresponding route.
\end{enumerate}\item On another occasion, Carol needs to go from her office to the Business Studies department $( B )$.
\begin{enumerate}[label=(\roman*)]
\item Write down her minimum walking time.
\item Write down the route corresponding to this minimum time.\\
\includegraphics[max width=\textwidth, alt={}, center]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-08_1499_1714_1208_153}
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 2011 Q4 [9]}}