PDSA Quiz 2: 16 August 2026 (May 2026 term)

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 there is a shorter path than the previous one.

2. B

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

3. C

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

4. D

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

1. A

   Only 1

2. B

   Only 2

3. C

   Both 1 and 2

4. D

   Neither 1 nor 2

1. A

   It can compute shortest paths only in graphs with non-negative edge weights.

2. B

   It computes shortest paths from a single source vertex to all other vertices.

3. C

   It computes shortest paths between every pair of vertices and can handle negative edge weights, provided there is no negative cycle.

4. D

   It requires the graph to be acyclic.