PDSA Quiz 2: 6 August 2023 (May 2023 term)

1. A

   This strategy will not solve the problem correctly.

2. B

   This strategy will only work if the graph is acyclic.

3. C

   This strategy will solve the problem correctly and is as efficient as Dijkstra’s algorithm.

4. D

   This strategy will solve the problem correctly, but is not as efficient as Dijkstra’s algorithm.

Select all that apply.

1. A

   Dijkstra’s algorithm may fail for graphs with negative weights because it does not reconsider a node once it marks it as visited, even if a shorter path exists than the previous one.

2. B

   The shortest path between two vertices u and v in a graph G always remains unaltered when all the edges of G are incremented by an equal amount.

3. C

   The shortest path between two vertices u and v in a graph G always remains unaltered when all the edges of G are multiplied by a positive integer.

4. D

   To decide which node to visit next, Dijkstra's algorithm selects the node with the smallest known distance.