| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2011 |
| Session | January |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Basic Dijkstra's algorithm application |
| Difficulty | Moderate -0.8 This is a straightforward application of Dijkstra's algorithm, a standard D1 procedure that students practice extensively. Part (a) requires mechanical execution of the algorithm (5 marks for showing working), parts (b) and (c) are direct read-offs from the completed table. No problem-solving insight or novel thinking required—purely algorithmic recall and careful arithmetic. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
1.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{0360f78d-e18c-4c47-a2ec-ddd705a4175f-2_750_1285_388_390}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
Figure 1 shows a network of roads between eight villages, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }$ and H . The number on each arc gives the length, in miles, of the corresponding road.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find the shortest distance from A to H .\\
(5)
\item State your shortest route.\\
(1)
\item Write down the shortest route from H to C and state its length.\\
(2)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2011 Q1 [8]}}