| Exam Board | OCR |
|---|---|
| Module | Further Discrete (Further Discrete) |
| Year | 2018 |
| Session | December |
| Marks | 12 |
| Topic | Shortest Path |
| Type | Network construction from matrix |
| Difficulty | Moderate -0.3 This is a straightforward application of standard Decision Maths techniques: drawing a network from given data, applying Dijkstra's algorithm (a routine procedure), and constructing a distance table. Part (c) requires minimal real-world reasoning about transport systems. While multi-part, each component is textbook-standard with no novel problem-solving required, making it slightly easier than average. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| From | to | Travel time |
| A | B | 5 |
| B | C | 3 |
| C | D | 9 |
| From | to | Travel time |
| B | F | 2 |
| F | E | 3 |
| E | D | 2 |
| From | to | Travel time |
| E | G | 5 |
| G | H | 6 |
| H | A | 4 |
| Answer | Marks | Guidance |
|---|---|---|
| 5 | 4 | 0 |
Question 5:
5 | 4 | 0 | 15 A rapid transport system connects 8 stations using three railway lines.\\
The blue line connects A to B to C to D .
\begin{center}
\begin{tabular}{ | c | c | c | }
\hline
From & to & Travel time \\
\hline
A & B & 5 \\
\hline
B & C & 3 \\
\hline
C & D & 9 \\
\hline
\end{tabular}
\end{center}
The red line connects $B$ to $F$ to $E$ to $D$.
\begin{center}
\begin{tabular}{ | c | c | c | }
\hline
From & to & Travel time \\
\hline
B & F & 2 \\
\hline
F & E & 3 \\
\hline
E & D & 2 \\
\hline
\end{tabular}
\end{center}
The green line connects E to G to H to A .
\begin{center}
\begin{tabular}{ | c | c | c | }
\hline
From & to & Travel time \\
\hline
E & G & 5 \\
\hline
G & H & 6 \\
\hline
H & A & 4 \\
\hline
\end{tabular}
\end{center}
\begin{itemize}
\item The travel times for the return journeys are the same as for the outward journeys (so, for example, the travel time from B to A is 5 minutes, the same as the time from A to B ).
\item All travel times include time spent stopped at stations.
\item No trains are delayed so the travel times are all correct.
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Model the blue, red and green lines, and the travel times above, as a network.
\item Use Dijkstra's algorithm to find the quickest travel times from C to each of the other stations.
\end{enumerate}\item \begin{enumerate}[label=(\roman*)]
\item Write down a route from A to D with travel time 12 minutes.
\item Construct a table of quickest travel times.
\end{enumerate}\item Give a reason why the quickest journey from A to D may take longer than 12 minutes.
\end{itemize}
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete 2018 Q5 [12]}}