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

×