AQA D1 2010 January — Question 7

Exam BoardAQA
ModuleD1 (Decision Mathematics 1)
Year2010
SessionJanuary
TopicShortest Path

7 [Figure 2, printed on the insert, is provided for use in this question.]
The following network has 13 vertices and 24 edges connecting some pairs of vertices. The number on each edge is its weight. The weights on the edges \(G K\) and \(L M\) are functions of \(x\) and \(y\), where \(x > 0 , y > 0\) and \(10 < x + y < 27\).
\includegraphics[max width=\textwidth, alt={}, center]{f99fad35-3304-4e8f-be02-1439dfdc10e1-7_1218_1431_660_312} There are three routes from \(A\) to \(M\) of the same minimum total weight.
  1. Use Dijkstra's algorithm on Figure 2 to find this minimum total weight.
  2. Find the values of \(x\) and \(y\).