| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2002 |
| Session | November |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra with route via intermediate vertex |
| Difficulty | Moderate -0.3 This is a standard D1 Dijkstra's algorithm question with straightforward application. Part (a) is routine algorithmic execution, part (b) tests basic understanding of backtracking, and part (c) requires running the algorithm twice (S to H, then H to T) but involves no novel problem-solving. Slightly easier than average due to being a direct application of a well-practiced algorithm. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
5.
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\includegraphics[alt={},max width=\textwidth]{438a62e6-113c-428e-85bf-4b1cbecee0de-5_763_1490_348_242}
\end{center}
\end{figure}
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find the shortest route from $S$ to $T$ in Fig. 3. Show all necessary working in the boxes in the answer booklet. State your shortest route and its length.
\item Explain how you determined the shortest route from your labelling.
\item It is now necessary to go from $S$ to $T$ via $H$. Obtain the shortest route and its length.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2002 Q5 [10]}}