| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2001 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra with route via intermediate vertex |
| Difficulty | Moderate -0.3 Part (a) is a standard Dijkstra's algorithm application requiring systematic box-filling and path tracing—routine D1 content. Part (b) adds a constraint (visiting E) but only requires running Dijkstra twice (S to E, then E to T) or inspecting the existing solution, which is a straightforward extension rather than requiring novel problem-solving insight. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Dijkstra's algorithm applied correctly | M1 | Dijkstra's algorithm |
| Labels at \(S\), \(A\), \(B\), \(C\) correct | A1 | |
| Labels at \(O\), \(E\) correct | A1 | |
| Remaining labels correct | A1 | |
| Correct order of labelling | A1ft | |
| Total | (5) | |
| Trace back: include arc \(xy\) if \(y\) already included and weight of \(xy\) = final label of \(y\) - final label of \(x\) | B2 | |
| e.g. \(T \leftarrow F: 37 - 17 = 20\) (FT) | ||
| \(F \leftarrow C: 17 - 8 = 9\) (CF) | ||
| \(C \leftarrow S: 8 - 0 = 8\) (SC) | ||
| Shortest route: \(SCFT\), length \(37\) km | A1 | (3) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Need shortest path \(S\) to \(E\) plus \(ET\) | M1 | |
| Shortest path \(S\) to \(E\) is \(SCFE\), length \(30\) km (from above) | A1ft | |
| \(\therefore SCFET\), length \(38\) km | A1ft | (3) |
## Question 4:
### Part (a):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Dijkstra's algorithm applied correctly | M1 | Dijkstra's algorithm |
| Labels at $S$, $A$, $B$, $C$ correct | A1 | |
| Labels at $O$, $E$ correct | A1 | |
| Remaining labels correct | A1 | |
| Correct order of labelling | A1ft | |
| **Total** | **(5)** | |
| Trace back: include arc $xy$ if $y$ already included and weight of $xy$ = final label of $y$ - final label of $x$ | B2 | |
| e.g. $T \leftarrow F: 37 - 17 = 20$ (FT) | | |
| $F \leftarrow C: 17 - 8 = 9$ (CF) | | |
| $C \leftarrow S: 8 - 0 = 8$ (SC) | | |
| Shortest route: $SCFT$, length $37$ km | A1 | **(3)** |
### Part (b):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Need shortest path $S$ to $E$ plus $ET$ | M1 | |
| Shortest path $S$ to $E$ is $SCFE$, length $30$ km (from above) | A1ft | |
| $\therefore SCFET$, length $38$ km | A1ft | **(3)** |
---4. This question should be answered on the sheet provided in the answer booklet.
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\includegraphics[alt={},max width=\textwidth]{6d306129-6e1f-424a-b21c-1bf6434ee082-5_732_1238_446_391}
\end{center}
\end{figure}
The weighted network shown in Fig. 3 models the area in which Bill lives. Each vertex represents a town. The edges represent the roads between the towns. The weights are the lengths, in km , of the roads.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find the shortest route from Bill's home at $S$ to $T$. Complete all the boxes on the answer sheet and explain clearly how you determined the path of least weight from your labelling.
Bill decides that on the way to $T$ he must visit a shop in town $E$.
\item Obtain his shortest route now, giving its length and explaining your method clearly.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2001 Q4 [11]}}