| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2004 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra with route via intermediate vertex |
| Difficulty | Easy -1.2 This is a straightforward application of Dijkstra's algorithm, a standard D1 topic requiring only mechanical execution of the algorithm on a small network. Part (a) is pure procedure, part (b) requires simple backtracking, and part (c) needs basic reasoning about combining two shortest paths. No novel insight or complex problem-solving is required—this is below average difficulty even for A-level. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
\includegraphics{figure_1}
Figure 1 shows a network of roads. The number on each edge gives the time, in minutes, to travel along that road. Avinash wishes to travel from $S$ to $T$ as quickly as possible.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find the shortest time to travel from $S$ to $T$. [4]
\item Find a route for Avinash to travel from $S$ to $T$ in the shortest time. State, with a reason, whether this route is a unique solution. [2]
\end{enumerate}
On a particular day Avinash must include $C$ in his route.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{2}
\item Find a route of minimal time from $S$ to $T$ that includes $C$, and state its time. [2]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2004 Q2 [8]}}