| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2012 |
| Session | January |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra combined with Chinese Postman |
| Difficulty | Moderate -0.8 This is a standard D1 question testing routine application of Dijkstra's algorithm and the route inspection (Chinese Postman) algorithm. Part (i) is algorithmic bookwork with no problem-solving required. Parts (ii) and (iii) are textbook applications of the route inspection algorithm with minimal adaptation. The question requires careful execution but no novel insight or complex reasoning. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04e Route inspection: Chinese postman, pairing odd nodes |
\includegraphics{figure_3}
\begin{enumerate}[label=(\roman*)]
\item Apply Dijkstra's algorithm to the copy of this network in the answer booklet to find the least weight path from A to F. State the route of the path and give its weight. [6]
\end{enumerate}
In the remainder of this question, any least weight paths required may be found without using a formal algorithm.
\begin{enumerate}[label=(\roman*)]
\setcounter{enumi}{1}
\item Apply the route inspection algorithm, showing all your working, to find the weight of the least weight closed route that uses every arc at least once. [3]
\item Find the weight of the least weight route that uses every arc at least once, starting at A and ending at F. Explain how you reached your answer. [4]
\end{enumerate}
\hfill \mbox{\textit{OCR D1 2012 Q3 [13]}}