| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2005 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra with vertex or edge exclusion |
| Difficulty | Easy -1.2 This is a straightforward application of Dijkstra's algorithm, a standard D1 topic requiring only mechanical execution of a learned procedure. Part (a) is routine algorithmic work, part (b) tests basic understanding of the method, and part (c) is a simple modification. No problem-solving insight or novel reasoning is required—just careful arithmetic and following the algorithm steps. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks |
|---|---|
| Network diagram with route: A C F E G J, length: 53 km | M1, A1, A1∧, A1∧, A1 |
| Answer | Marks | Guidance |
|---|---|---|
| General explanation – Trace back from J: include arc x,y if ∀ already on path and if difference is 'just label equal length of arc. | B2, 1, 0 | |
| Specific explanation – \(53 - 15 = 38\) GJ; \(38 - 6 = 32\) EG; \(32 - 4 = 28\) FE; \(28 - 10 = 18\) CF; \(18 - 18 = 0\) AC |
| Answer | Marks | Guidance |
|---|---|---|
| e.g. ADFEGJ or ACEGJ; length 54 km | m1, a1; @(2) |
| Answer | Marks |
|---|---|
| 6(a)M1 | In E or F or G or H or I w.v. large replaced by ismals .1 |
| A1 | A, B, C, D, F comect (order in routing sequence) |
| A1 ∧ | E, G, I comect + labelling order (pends order of labelling only one) |
| A1 ∧ | H, J comect + labelling (pends order of labelling only one) |
| A1 | Route + length (LLoH) candour lack of km. |
| B2 ∧ | complete version of one of the 2 given explanation |
| B1 ∧ | all the bar one step. 'bad set B1' |
| C) m1 | Route h to J aviding CF |
| A1 | c.a.o or a description |
| A1 | 54 (condore lack of km) |
## Part (a)
| Network diagram with route: A C F E G J, length: 53 km | M1, A1, A1∧, A1∧, A1 | |
## Part (b)
| **General explanation** – Trace back from J: include arc x,y if ∀ already on path and if difference is 'just label equal length of arc. | | B2, 1, 0 |
| **Specific explanation** – $53 - 15 = 38$ GJ; $38 - 6 = 32$ EG; $32 - 4 = 28$ FE; $28 - 10 = 18$ CF; $18 - 18 = 0$ AC | | |
## Part (c)
| e.g. ADFEGJ or ACEGJ; length 54 km | | m1, a1; @(2) |
### Notes
| **6(a)M1** | In E or F or G or H or I w.v. large replaced by ismals .1 | | |
| **A1** | A, B, C, D, F comect (order in routing sequence) | | |
| **A1 ∧** | E, G, I comect + labelling order (pends order of labelling only one) | | |
| **A1 ∧** | H, J comect + labelling (pends order of labelling only one) | | |
| **A1** | Route + length (LLoH) candour lack of km. | | |
| **B2 ∧** | complete version of one of the 2 given explanation | | |
| **B1 ∧** | all the bar one step. 'bad set B1' | | |
| **C)** m1 | Route h to J aviding CF | | |
| | **A1** | c.a.o or a description | | |
| | | A1 | 54 (condore lack of km) | | |
---\includegraphics{figure_5}
Figure 5 shows a network of roads. The number on each arc represents the length of that road in km.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find the shortest route from $A$ to $J$. State your shortest route and its length. [5]
\item Explain how you determined the shortest route from your labelled diagram. [2]
\end{enumerate}
The road from $C$ to $F$ will be closed next week for repairs.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{2}
\item Find the shortest route from $A$ to $J$ that does not include $CF$ and state its length. [3]
\end{enumerate}
(Total 10 marks)
\hfill \mbox{\textit{Edexcel D1 2005 Q6 [10]}}