Quiz Space

Programming, Data Structures and Algorithms using Python · Quiz 2 · 23 Nov 2025 · September 2025 term

Question 2: Consider the following algorithm to solve the single sour…

Question 2

+3 marksOne correct option

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.

  1. A

    I is True but II is False

  2. B

    I is False but II is True

  3. C

    Both I and II are False

  4. D

    Both I and II are True

Show answer

Correct answer

  • A

    I is True but II is False

See the whole paperTake it as a mock test

Question 2 of 16 in the IIT Madras BS Programming, Data Structures and Algorithms using Python (PDSA) Quiz 2 paper sat on 23 Nov 2025, in the September 2025 term (IIT M DIPLOMA AN EXAM QDD2 23 Nov 2025 NEW). It carries 3 marks.

More questions from this paper

  1. Q1In the given graph, if we try to find the shortest path from node P to all other nodes using Dijkstra’s algorithm, whic…
  2. Q3What is the weight of a minimum spanning tree in the graph given below?
  3. Q4Let\ be a connected undirected graph with distinct positive edge weights.Consider a partition (cut) of the vertex set\ …
  4. Q5Consider a max-heap of size\ consisting of distinct elements and implemented using an array. Which of the following ope…
  5. Q6Consider a max-heap of size\ consisting of distinct elements and implemented using an array.Which of the following stat…
  6. Q7The height of a binary search tree is defined as the number of nodes in the longest path from the root to the leaf (bot…
  7. Q8The height of a binary search tree is defined as the number of nodes in the longest path from the root to the leaf (bot…
  8. Q9What is the minimum number of nodes possible in an AVL tree of height 6 ? Consider the tree with a single node having h…
  9. Q10After inserting the following elements into an empty AVL Tree:\ 30, 20, 10, 28, 25, 40\ Which of the following nodes wi…
  10. Q11Given below is a set of characters and their frequencies: Using Huffman encoding, construct the Huffman tree for this s…
  11. Q12Consider a problem scenario where you have to conduct\ job interviews\ . Each candidate is available only between start…
  12. Q13In an integer list L of length n, two elements L[i] and L[j] form an inversion if L[i] > L[j] and i \< j. Consider a li…
  13. Q14Which of the following statements is incorrect?
  14. Q15Consider the following recursive function to return the minimum element in the list L of size n. def find_min(L, low, h…
  15. Q16Consider the following recurrences and choose the correct option. 1. 2. Base Case: