| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Practical modelling questions |
| Difficulty | Moderate -0.3 This is a standard Dijkstra's algorithm application question from D1, requiring systematic execution of a well-defined procedure on a moderate-sized network. While it requires careful bookkeeping and a written explanation of method, it involves no novel problem-solving or conceptual insight beyond routine algorithmic application. Part (c) is trivial contextualisation. Slightly easier than average A-level due to being purely procedural. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| (a) Label \(J\) – label \(I = 5\) = weight \(IJ\); label \(I\) – label \(G = 8\) = weight \(GI\); label \(G\) – label \(E = 3\) = weight \(EG\); label \(E\) – label \(A = 10\) = weight \(AE\); so \(A \equiv E \equiv I \equiv J\) is path of least weight, weight = 26 | M1 A1, A2 | |
| (b) There are no other paths of least weight; these would have been revealed by the backward scan | B1, B1 | |
| (c) e.g. finding shortest distance by road between two towns | B1 | (12) |
**(a)** Label $J$ – label $I = 5$ = weight $IJ$; label $I$ – label $G = 8$ = weight $GI$; label $G$ – label $E = 3$ = weight $EG$; label $E$ – label $A = 10$ = weight $AE$; so $A \equiv E \equiv I \equiv J$ is path of least weight, weight = 26 | M1 A1, A2 |
**(b)** There are no other paths of least weight; these would have been revealed by the backward scan | B1, B1 |
**(c)** e.g. finding shortest distance by road between two towns | B1 | (12)
---5. This question should be answered on the sheet provided.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-05_834_1436_306_280}
\captionsetup{labelformat=empty}
\caption{Fig. 3}
\end{center}
\end{figure}
Figure 3 shows a weighted network. The number on each arc indicates the weight of that arc.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find a path of least weight from $A$ to $J$ and state the weight of the path.
Your solution must show clearly how you have applied the algorithm including:
\begin{enumerate}[label=(\roman*)]
\item the order in which the vertices were labelled,
\item how you determined the path of least weight.
\end{enumerate}\item Find if there are any other paths of least weight and explain your answer.
\item Describe a practical problem that could be modelled by the above network.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 Q5 [12]}}