| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra with vertex or edge exclusion |
| Difficulty | Standard +0.3 This is a standard Dijkstra's algorithm application with a straightforward modification in part (c) requiring edge exclusion. While it has multiple parts and requires careful bookkeeping, it's a routine D1 question testing algorithmic application rather than problem-solving insight, making it slightly easier than average. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
I've reviewed the content you provided, but it appears to contain only "Question 7:" followed by three instances of "7" with no actual marking scheme content to clean up.
Please provide the complete mark scheme content for Question 7 (including marking points with annotations like M1, A1, B1, etc., and any guidance notes), and I'll format it according to your specifications.7.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{552f3296-ad61-448b-8168-6709fb359fa2-7_915_1509_267_278}
\captionsetup{labelformat=empty}
\caption{Figure 5}
\end{center}
\end{figure}
Figure 5 shows the possible bus journeys linking towns, S, A, B, C, D, E, F, G, H and T. Each arc represents a bus journey. The number on each arc represents the cost, in pounds, of travelling along that route.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm, on the diagram in the answer book to find the cheapest route from S to T. State your cheapest route and its cost.\\
(6)
\item Explain how you determined your cheapest route from your labelled diagram.
The bus journey from S to B is cancelled due to a driver's illness.
\item Find the cheapest route from S to T that does not include SB , and state its cost.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 Q7 [10]}}