OCR D1 2011 June — Question 5 14 marks

Exam BoardOCR
ModuleD1 (Decision Mathematics 1)
Year2011
SessionJune
Marks14
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicShortest Path
TypeDijkstra with vertex or edge exclusion
DifficultyStandard +0.3 This is a standard D1 Dijkstra's algorithm question with routine extensions. Part (i) is textbook application, parts (ii)-(iii) require basic analysis of how changing one edge weight affects the algorithm (standard D1 fare), and part (iv) is simple quadratic scaling arithmetic. All parts follow predictable patterns with no novel problem-solving required.
Spec7.04a Shortest path: Dijkstra's algorithm7.04f Network problems: choosing appropriate algorithm
5 The arcs in the network below represent the tracks in a forest and the weights on the arcs represent distances in km. \includegraphics[max width=\textwidth, alt={}, center]{cec8d4db-4a72-43a3-88f3-ff9df2a11d2c-6_543_1269_392_438} Dijkstra's algorithm is to be used to find the shortest path from \(A\) to \(G\).
  1. Apply Dijkstra's algorithm to find the shortest path from \(A\) to \(G\). Show your working, including temporary labels, permanent labels and the order in which permanent labels are assigned. Do not cross out your working values. Write down the route of the shortest path from \(A\) to \(G\) and give its length. The track joining \(B\) and \(D\) is washed away in a flood. It is replaced by a new track of unknown length, \(x \mathrm {~km}\). \includegraphics[max width=\textwidth, alt={}, center]{cec8d4db-4a72-43a3-88f3-ff9df2a11d2c-6_544_1271_1480_438}
  2. What is the smallest value that \(x\) can take so that the route found in part (i) is still a shortest path? If the value of \(x\) is smaller than this, what is the weight of the shortest path from \(A\) to \(G\) ?
  3. (a) For what values of \(x\) will vertex \(E\) have two temporary labels? Write down the values of these temporary labels.
    (b) For what values of \(x\) will vertex \(C\) have two temporary labels? Write down the values of these temporary labels. Dijkstra's algorithm has quadratic order.
  4. If a computer takes 20 seconds to apply Dijkstra's algorithm to a complete network with 50 vertices, approximately how long will it take for a complete network with 100 vertices?
AnswerMarks
(iii) Column required in part (iii)[5]
A column of 0 > M_0
(answer (ii) below on scan) An augmented labelleth four basis column non-negative values in final columnM1 A1
Correct tableau below on scanB1 B1
Condone 3.5 identify without 6.2 as well
Condone 1.8 identify without 4.3 as well 
(iii) Column required in part (iii) | [5] |

A column of 0 > M_0 | |

(answer (ii) below on scan) An augmented labelleth four basis column non-negative values in final column | M1 A1 |

Correct tableau below on scan | B1 B1 |

Condone 3.5 identify without 6.2 as well | |

Condone 1.8 identify without 4.3 as well | |

---
5 The arcs in the network below represent the tracks in a forest and the weights on the arcs represent distances in km.\\
\includegraphics[max width=\textwidth, alt={}, center]{cec8d4db-4a72-43a3-88f3-ff9df2a11d2c-6_543_1269_392_438}

Dijkstra's algorithm is to be used to find the shortest path from $A$ to $G$.
\begin{enumerate}[label=(\roman*)]
\item Apply Dijkstra's algorithm to find the shortest path from $A$ to $G$. Show your working, including temporary labels, permanent labels and the order in which permanent labels are assigned. Do not cross out your working values. Write down the route of the shortest path from $A$ to $G$ and give its length.

The track joining $B$ and $D$ is washed away in a flood. It is replaced by a new track of unknown length, $x \mathrm {~km}$.\\
\includegraphics[max width=\textwidth, alt={}, center]{cec8d4db-4a72-43a3-88f3-ff9df2a11d2c-6_544_1271_1480_438}
\item What is the smallest value that $x$ can take so that the route found in part (i) is still a shortest path? If the value of $x$ is smaller than this, what is the weight of the shortest path from $A$ to $G$ ?
\item (a) For what values of $x$ will vertex $E$ have two temporary labels? Write down the values of these temporary labels.\\
(b) For what values of $x$ will vertex $C$ have two temporary labels? Write down the values of these temporary labels.

Dijkstra's algorithm has quadratic order.
\item If a computer takes 20 seconds to apply Dijkstra's algorithm to a complete network with 50 vertices, approximately how long will it take for a complete network with 100 vertices?
\end{enumerate}

\hfill \mbox{\textit{OCR D1 2011 Q5 [14]}}
This paper (6 questions)
View full paper
Q1 6 Q2 8 Q3 9 Q4 13 Q5 14 Q6 22