| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2014 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra with route via intermediate vertex |
| Difficulty | Moderate -0.5 Part (a) is a standard application of Dijkstra's algorithm, a routine procedure taught in D1. Part (b) requires comparing two shortest paths (S→E→T vs the original), which adds minimal complexity. This is a textbook exercise testing algorithmic execution rather than problem-solving insight, making it easier than average A-level questions overall. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
3.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{23cc3c59-35d8-4120-9965-952c0ced5b3d-4_605_1378_248_370}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{center}
\end{figure}
Figure 3 represents a network of roads. The number on each arc represents the time taken, in minutes, to traverse each road.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find the quickest route from S to T. State your quickest route and the time taken.\\
(6)
It is now necessary to include E in the route.
\item Determine the effect that this will have on the time taken for the journey. You must state your new quickest route and the time it takes.\\
(3)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2014 Q3 [9]}}