Algorithmic complexity calculations

A question is this type if and only if it asks to calculate the time required to run an algorithm (typically Dijkstra's) for different network sizes, given that the algorithm has order n².

5 questions · Standard +0.3

7.04a Shortest path: Dijkstra's algorithm
Sort by: Default | Easiest first | Hardest first
OCR D1 2013 June Q5
15 marks Standard +0.3
5 This question uses the same network as question 4. The total weight of the arcs in the network is 224. \includegraphics[max width=\textwidth, alt={}, center]{dbefedb2-b398-45e8-92eb-eb510ff16def-5_618_1415_310_319}
  1. Apply Dijkstra's algorithm to the network, starting at \(A\), to find the shortest route from \(A\) to \(G\).
  2. 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 to apply Dijkstra's algorithm to a network with 1400 vertices.
  3. How much shorter would the path \(C E\) need to be for it to become part of a shortest path from \(A\) to \(G\) ? Following a landslip, the paths \(A C\) and \(C E\) become blocked and cannot be used. A warden needs to travel along all the remaining paths to check that there are no more landslips.
  4. Find the shortest distance that the warden must travel, assuming that she starts and ends at vertex \(C\). Show your working.
OCR Further Discrete 2022 June Q7
12 marks Challenging +1.2
7 A building has 7 CCTV cameras, A to G, at the junctions of some of the corridors.
The cameras at the junctions and the lengths of the 11 corridors between them, in metres, are shown in the table below.
ABCDEFG
A6460111
B6472103
C606658
D111726632127
E1033282
F5812775
G8275
  1. Model this information as a network.
  2. Use an appropriate algorithm to calculate the minimum distance from A to each of the other vertices. The run-time of an algorithm for finding this minimum distance is proportional to the total number of comparisons used. For a network with \(n\) vertices, the worst case is when the algorithm is applied to a network based on the complete graph \(\mathrm { K } _ { n }\). In each pass
    • A vertex is made permanent and the temporary label at all adjacent vertices that are not yet permanent are updated. This uses 1 comparison for every such vertex (adjacent to the permanent label) that previously already had a temporary label.
    • The best temporary labels at all vertices that do not yet have permanent labels are then compared to determine the next vertex to become permanent. If there are \(k\) such vertices this involves \(k - 1\) comparisons.
    • By considering the number of comparisons of each type in each iteration, show that the algorithm uses a total of 6 comparisons when it is applied to a network based on the complete graph \(\mathrm { K } _ { 4 }\).
    You are given that the total number of comparisons used when the algorithm is applied to a network based on \(\mathrm { K } _ { n }\) is \(( n - 1 ) ( n - 2 )\). A computer takes 0.03 seconds to apply this algorithm on a network based on \(\mathrm { K } _ { 7 }\).
  3. Calculate, to \(\mathbf { 1 }\) decimal place, how many seconds it will take the computer to apply the algorithm to a network based on \(\mathrm { K } _ { 70 }\). \section*{Question 7 continues on the next page} The manager wants to construct a tour (a closed route) that passes each camera.
    1. Find a lower bound for the length of this tour by initially deleting D .
    2. Find an upper bound for the length of this tour by using the nearest neighbour algorithm starting from D.
    3. Deduce the length of the shortest possible tour. Briefly explain your reasoning. \section*{END OF QUESTION PAPER}
Edexcel FD1 AS 2018 June Q1
9 marks Moderate -0.5
1. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{3e853c6d-e90e-4a09-b990-1c2c146b54e1-2_1105_1459_463_402} \captionsetup{labelformat=empty} \caption{Figure 1}
\end{figure} Figure 1 represents a network of roads.
The number on each arc represents the time taken, in minutes, to drive along the corresponding road.
    1. Use Dijkstra's algorithm to find the shortest time needed to travel from A to H .
    2. State the quickest route. For a network with \(n\) vertices, Dijkstra's algorithm has order \(n ^ { 2 }\)
  2. If it takes 1.5 seconds to run the algorithm when \(n = 250\), calculate approximately how long it will take, in seconds, to run the algorithm when \(n = 9500\). You should make your method and working clear.
  3. Explain why your answer to part (b) is only an approximation.
Edexcel FD1 2021 June Q6
10 marks Standard +0.3
6. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{43bc1e60-d8b2-4ea5-9652-4603a26c2f78-07_728_1465_248_301} \captionsetup{labelformat=empty} \caption{Figure 4}
\end{figure} In Figure 4 the weights on the arcs represent distances.
    1. Use Dijkstra's algorithm to find the shortest path from A to H .
    2. State the length of the shortest path from A to H . One application of Dijkstra's algorithm has order \(n ^ { 2 }\), where \(n\) is the number of nodes in the network. A computer produces a table of shortest distances between any two different nodes by repeatedly applying Dijkstra's algorithm from each node of the network. It takes the computer 0.082 seconds to produce a table of shortest distances for a network of 10 nodes.
  2. Calculate approximately how long it will take, in seconds, for the computer to produce a table of shortest distances for a network with 200 nodes. You must give a reason for your answer.
  3. Explain why your answer to part (b) can only be an approximation.
Edexcel FD1 2023 June Q3
8 marks Standard +0.3
3. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6ccce35f-4e62-4b6b-acf6-f9b3e18d4b52-05_862_1460_219_299} \captionsetup{labelformat=empty} \caption{Figure 4}
\end{figure} Figure 4 represents a network with nodes, A, B, C, D, E, F, G, H and J.
The number on each edge gives the length of the corresponding edge.
    1. Use Dijkstra's algorithm to find the shortest path from A to J.
    2. State the length of the shortest path from A to J . One application of Dijkstra's algorithm has order \(n ^ { 2 }\), where \(n\) is the number of nodes in the network. It takes a computer 0.0312 seconds to find the shortest path from a given start node to a given end node in a network of 9 nodes.
  2. Calculate approximately how long it would take, in minutes, for the computer to find the shortest path from a given start node to a given end node for a network of 9000 nodes.