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

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

**Your answer seems reasonable.**Find out if you're right!

**That seems reasonable.**Find out if you're right!

Already have an account? Log in here.