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

**Computer Science**Level 5

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.**