OCR FD1 AS 2018 March — Question 2 8 marks

Exam BoardOCR
ModuleFD1 AS (Further Decision 1 AS)
Year2018
SessionMarch
Marks8
TopicShortest Path
TypeIncomplete Dijkstra reconstruction
DifficultyStandard +0.8 This question requires reverse-engineering Dijkstra's algorithm from partial information, demanding deep understanding of how the algorithm works rather than just executing it. Students must work backwards to deduce missing arc weights and handle the non-standard scenario of multiple shortest paths, which goes beyond routine application and requires genuine problem-solving insight.
Spec7.04a Shortest path: Dijkstra's algorithm
2 The diagram shows an incomplete solution to the problem of using Dijkstra's algorithm to find a shortest path from \(A\) to \(F\). Any cell that has values in it is complete. \includegraphics[max width=\textwidth, alt={}, center]{a51b112d-1f3f-4214-94c1-8b9cd7eb831c-2_650_1246_1107_411}
  1. (a) Find the missing weight on \(\operatorname { arc } B E\).
    (b) What can you deduce about the missing weight on arc \(C D\) ? You are now given that the weight of arc \(C E\) is not 3 .
  2. (a) What can you deduce about the missing weight on arc \(C E\) ?
    (b) Complete the labelling of the boxes at \(E\) and \(F\) on the diagram in the Printed Answer Booklet. [2] Suppose that there are two shortest routes from \(A\) to \(F\).
  3. Show how trace back is used to find the shortest routes from \(A\) to \(F\).
Question 2:
AnswerMarks
26
7 6
12 9
Question 2:
2 | 6
7 6
12 9
2 The diagram shows an incomplete solution to the problem of using Dijkstra's algorithm to find a shortest path from $A$ to $F$. Any cell that has values in it is complete.\\
\includegraphics[max width=\textwidth, alt={}, center]{a51b112d-1f3f-4214-94c1-8b9cd7eb831c-2_650_1246_1107_411}
\begin{enumerate}[label=(\roman*)]
\item (a) Find the missing weight on $\operatorname { arc } B E$.\\
(b) What can you deduce about the missing weight on arc $C D$ ?

You are now given that the weight of arc $C E$ is not 3 .
\item (a) What can you deduce about the missing weight on arc $C E$ ?\\
(b) Complete the labelling of the boxes at $E$ and $F$ on the diagram in the Printed Answer Booklet. [2]

Suppose that there are two shortest routes from $A$ to $F$.
\item Show how trace back is used to find the shortest routes from $A$ to $F$.
\end{enumerate}

\hfill \mbox{\textit{OCR FD1 AS 2018 Q2 [8]}}
This paper (6 questions)
View full paper
Q1 10 Q2 8 Q3 9 Q4 9 Q5 8 Q6 16