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.

Problem Loading...

Note Loading...

Set Loading...