OCR A Level: Decision 1 - Dijkstra's Algorithm [June 2013 Q5]

It is given that the total weight of the arcs in the network below is 224.

$(\text{i})$ Apply Dijkstra's algorithm to the network, starting at $A$ , to find the shortest route from $A$ to $G$ .

$(\text{ii})$ Dijkstra's algorithm has quadratic order (order $n^2$ ). It takes 2.25 seconds for a certain computer to apply Dijkstra's algorithm to a network with 7 vertices. Calculate approximately how many hours it will take for a 1400 vertex network.

$(\text{iii})$ How much shorter would the path $CE$ need to be for it to become part of a shortest path from $A$ to $G$ ?

$(\text{iv})$ Given $AC$ and $CE$ become blocked, find the shortest distance that one must travel to travel along all the remaining arcs, starting and ending at $C$ . Show your working.

---

Input the shortest distance from part $(\text{iv})$ as your answer.

---

There are 5 marks available for part (i), 2 marks for part (ii), 2 marks for part (iii) and 6 marks for part (ii).

In total, this question is worth 20.8% of all available marks in the paper.

---

This is part of the set OCR A Level Problems .