Edexcel D1 2002 January — Question 3

Exam BoardEdexcel
ModuleD1 (Decision Mathematics 1)
Year2002
SessionJanuary
TopicShortest Path

  1. State the number of edges in a minimum spanning tree for \(N\). A minimum spanning tree for a connected network has \(n\) edges.
  2. State the number of vertices in the network. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{2f4d2383-823a-4a6f-ad4b-69cf01566052-4_714_1129_380_476}
    \end{figure} Figure 1 shows a network of roads. Erica wishes to travel from \(A\) to \(L\) as quickly as possible. The number on each edge gives the time, in minutes, to travel along that road.
  3. Use Dijkstra's algorithm to find a quickest route from \(A\) to \(L\). Complete all the boxes on the answer sheet and explain clearly how you determined the quickest route from your labelling.
  4. Show that there is another route which also takes the minimum time