| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2021 |
| Session | October |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra with route via intermediate vertex |
| Difficulty | Moderate -0.8 This is a straightforward application of Dijkstra's algorithm with standard bookwork definition and a simple constraint (via G). Part (a) is pure recall, part (b) is routine algorithm application worth 6 marks, and part (c) requires minimal adaptation (running Dijkstra twice or inspecting the existing solution). No novel problem-solving or insight required beyond textbook procedures. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
\begin{enumerate}
\item (a) Explain what is meant by the term 'path'.\\
(2)
\end{enumerate}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{d409aaae-811d-4eca-b118-efc927885f97-02_812_1262_427_404}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
Figure 1 represents a network of roads. The number on each arc represents the length, in km, of the corresponding road. Piatrice wishes to travel from A to J.\\
(b) Use Dijkstra's algorithm to find the shortest path Piatrice could take from A to J. State your path and its length.\\
(6)
Piatrice needs to return from J to A via G.\\
(c) Find the shortest path Piatrice could take from J to A via G and state its length.\\
\hfill \mbox{\textit{Edexcel D1 2021 Q1 [10]}}