| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2015 |
| Session | June |
| 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 Dijkstra's algorithm application with a straightforward extension requiring a route through a specific vertex. Part (a) is routine algorithmic execution, part (b) tests understanding of the method, and part (c) requires running Dijkstra twice (A to E, then E to J) or careful inspection—all well-practiced techniques in D1 with no novel problem-solving required. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
3.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{ba22b22e-c0d5-438d-821b-88619eacdb5d-4_901_894_228_612}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{center}
\end{figure}
Figure 3 represents a network of roads. The number on each arc is the length, in km , of the corresponding road.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find the shortest route from A to J. State the shortest route and its length.
\item Explain how you determined the shortest route from your labelled diagram.
\item Find the shortest route from A to J via E and state its length.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2015 Q3 [10]}}