PDSA Quiz 2: 23 November 2025 (September 2025 term)

In the given graph, if we try to find the shortest path from node P to all other nodes using

Dijkstra’s algorithm, which node is the
node to be included in the visited set? Consider that P is the 1st visited node.

Consider the following algorithm to solve the single source shortest path problem for a graph (directed or undirected) with positive integer edge weights and a source vertex s.Replace each edge (u,v) of weight w in the graph with a path of length w consisting of unit-weight edges from u to v (by introducing new intermediate vertices).
For example: edge (u, v) with weight w = 3

Run BFS on this modified graph from the source s to find the shortest path to each of the original vertices in the graph.
Which of the following statements is/are true?
I. The algorithm solves the single source shortest path problem correctly.
II. Although the size of the modified graph is larger than the original graph, the algorithm is as efficient as Dijkstra’s algorithm.

What is the weight of a minimum spanning tree in the graph given below?