| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2016 |
| Session | June |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra with route via intermediate vertex |
| Difficulty | Standard +0.3 This is a standard application of Dijkstra's algorithm followed by routine extensions. Part (i) is textbook Dijkstra, part (ii) requires simple comparison of two paths via K or L, and part (iii) is standard route inspection algorithm. All are algorithmic procedures with minimal problem-solving insight required, making this slightly easier than average. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Dijkstra's algorithm applied systematically from G | M1 | Correct method |
| Working values updated correctly at each vertex | A1 | |
| Final labels: correct shortest distances assigned | A1 | |
| Shortest distance = 17 km | A1 | |
| Route: G – H – K – L – N | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Need to include arc KL; from part (i) working, find shortest path G→K + KL + L→N or G→L + LK + K→N | M1 | Using Dijkstra results |
| Route: G – H – K – L – N already includes KL, distance = 17 km | A1 |
| Answer | Marks |
|---|---|
| Identify odd-order vertices | M1 |
| Odd vertices: find which vertices have odd degree from the network | A1 |
| Find minimum weight pairing of odd vertices | M1 |
| Arcs to repeat identified correctly | A1 |
| Minimum distance = \(60 +\) repeated arcs total; state how many times L is passed through | A1 |
# Question 5:
**(i)**
| Dijkstra's algorithm applied systematically from G | M1 | Correct method |
| Working values updated correctly at each vertex | A1 | |
| Final labels: correct shortest distances assigned | A1 | |
| Shortest distance = **17 km** | A1 | |
| Route: **G – H – K – L – N** | A1 | |
**(ii)**
| Need to include arc KL; from part (i) working, find shortest path G→K + KL + L→N or G→L + LK + K→N | M1 | Using Dijkstra results |
| Route: **G – H – K – L – N** already includes KL, distance = 17 km | A1 | |
**(iii)**
| Identify odd-order vertices | M1 | |
| Odd vertices: find which vertices have odd degree from the network | A1 | |
| Find minimum weight pairing of odd vertices | M1 | |
| Arcs to repeat identified correctly | A1 | |
| Minimum distance = $60 +$ repeated arcs total; state how many times L is passed through | A1 | |
---5 The network below represents a single-track railway system. The vertices represent stations, the arcs represent railway tracks and the weights show distances in km.
The total length of the arcs shown is 60 km .\\
\includegraphics[max width=\textwidth, alt={}, center]{d783915d-5950-4a97-b6a0-70959214e218-5_442_1152_429_459}\\
\begin{enumerate}[label=(\roman*)]
\item Apply Dijkstra's algorithm to the network, starting at $G$, to find the shortest distance (in km ) from $G$ to $N$ and write down the route of this shortest path.
Greg wants to travel from the station represented by vertex $G$ to the station represented by vertex $N$. He especially wants to include the track $K L$ (in either direction) in his journey.
\item Show how to use your working from part (i) to find the shortest journey that Greg can make that fulfils his requirements. Write down his route.
Percy Li needs to check each track to see if any maintenance is required. He wants to start and end at the station represented by vertex $G$ and travel in one continuous route that passes along each track at least once. The direction of travel along the tracks does not matter.
\item Apply the route inspection algorithm, showing your working, to find the minimum distance that Percy will need to travel. Write down those arcs that Percy will need to repeat. If he travels this minimum distance, how many times will Percy travel through the station represented by vertex $L$ ?
\end{enumerate}
\hfill \mbox{\textit{OCR D1 2016 Q5 [12]}}