3D.2.2 Shortest paths: Dijkstra's and Floyd's algorithms Quiz: Pearson Edexcel Further Maths, Unit 36

The 20 questions

1. Dijkstra's algorithm finds

   • shortest paths from one source vertex to all other vertices
   • all-pairs shortest paths only
   • the longest path in the network
   • a minimum spanning tree

2. Dijkstra's algorithm requires edge weights to be

   • non-negative
   • all equal
   • whole numbers only
   • negative

3. Floyd's algorithm finds

   • the critical path
   • a minimum spanning tree
   • shortest paths between every pair of vertices
   • the shortest path from one vertex only

4. In iteration k of Floyd's algorithm, the route through vertex k is considered

   • only for the edges leaving vertex k
   • as the k-th shortest route between two vertices
   • for every pair of vertices, to see whether it shortens their current route
   • for vertices of degree k only

5. Dijkstra's algorithm labels each vertex with

   • its current shortest distance from the source and its predecessor
   • its colour only
   • its degree
   • its number of neighbours

6. The route matrix in Floyd's algorithm records

   • the next vertex on each shortest route
   • the degree of each vertex
   • the total number of edges
   • the weight of the minimum spanning tree

7. Dijkstra's algorithm is best described as

   • a greedy algorithm
   • a brute force search of all routes
   • a linear programming method
   • a random search method

8. A network has edges S-B 2, S-A 4, B-A 1, A-T 5 and B-T 8. What is the shortest distance from S to T?

   • 8
   • 10
   • 6
   • 9

9. Edges S-A 3, S-B 5, A-B 1, A-D 6 and B-D 2 form a network. What is the shortest distance from S to D?

   • 8
   • 7
   • 6
   • 9

10. Floyd's algorithm has d(2,1) = 4, d(1,3) = 5 and d(2,3) = infinity. What is d(2,3) after using vertex 1 as an intermediate?

    • 5
    • 4
    • 9
    • infinity

11. Dijkstra's algorithm starts at S with edges S-B 2 and S-A 4. Which vertex is permanently labelled first after S?

    • S, with distance 2
    • A, with distance 4
    • T, with distance 9
    • B, with distance 2

12. Why can Dijkstra's algorithm fail when a network has a negative edge?

    • it may label a vertex permanently before a shorter route through the negative edge is found
    • it works only on trees
    • it cannot handle whole-number weights
    • it counts edges rather than weights

13. A network has A-B 3, B-C 4 and a direct edge A-C of length 10. After Floyd's algorithm, what is the shortest distance from A to C?

    • 3
    • 7
    • 10
    • 4

14. Dijkstra's algorithm is run on a network with 6 vertices. How many vertices are permanently labelled in total?

    • 12
    • 5
    • 6
    • 36

15. Edges S-A 2, A-T 2, S-B 1 and B-T 4 form a network. What is the shortest distance from S to T?

    • 5
    • 6
    • 4
    • 3

16. Why, with non-negative weights, does Dijkstra's algorithm never need to revisit a permanently labelled vertex?

    • any later route to it is at least as long, since extending a route never shortens it
    • because the algorithm ends after one pass
    • because every vertex has the same label
    • because the graph has no cycles

17. A network has S-A 1, S-B 4, A-B 2, A-C 6, B-C 3 and C-T 1. What is the shortest distance from S to T?

    • 7
    • 9
    • 6
    • 8

18. Roughly how many table updates does Floyd's algorithm make on a network with n vertices?

    • 2^n
    • n log n
    • n^3
    • n^2

19. Why can Floyd's algorithm reveal a negative cycle?

    • it counts the number of edges
    • the graph becomes disconnected
    • a negative value appears on a diagonal entry d(i,i), meaning a route from i back to i is negative
    • all diagonal entries become zero

20. A network has S-A 3, S-B 7, A-B 2, A-C 4, B-C 1, C-T 3 and B-T 6. What is the shortest distance from S to T?

    • 9
    • 10
    • 13
    • 11

Related quizzes

• Minimum spanning trees: Prim's and Kruskal's algorithms Quiz · 3D.2.1 · 20 questions
• Proof by mathematical induction Quiz · 1.1 · 20 questions
• Quadratic equations and complex arithmetic Quiz · 2.1-2.2 · 20 questions
• Matrix arithmetic and inverses Quiz · 3.1-3.2 · 20 questions
• Expectation of discrete random variables Quiz · 3B.1.1 · 20 questions
• The Poisson distribution Quiz · 3B.2.1 · 20 questions
• Geometric and negative binomial models Quiz · 3B.3.1 · 20 questions
• Hypothesis tests for the Poisson distribution Quiz · 3B.4.1 · 20 questions
• Applying the Central Limit Theorem Quiz · 3B.5.1 · 20 questions
• Goodness of fit tests for discrete distributions Quiz · 3B.6.1 · 20 questions