Quiz Space

Programming in Python · Quiz 2 · 12 Apr 2026 · January 2026 term

Question 2: The Bellman–Ford algorithm can be used to detect the pres…

Question 2

+3 marksOne correct option

The Bellman–Ford algorithm can be used to detect the presence of a negative-weight cycle reachable from the source vertex in a weighted directed graph. Which of the following correctly explains how Bellman–Ford detects a negative-weight cycle?

  1. A

    A negative-weight cycle exists if the shortest distance to any vertex becomes negative at any point during the algorithm.

  2. B

    If, after performing exactly relaxation iterations, an additional relaxation of any edge further reduces a distance value, then a negative-weight cycle is present.

  3. C

    If the algorithm encounters an edge with a negative weight during relaxation, it immediately concludes that a negative-weight cycle exists.

  4. D

    If multiple shortest paths exist between two vertices, the graph must contain a negative-weight cycle.

Show answer

Correct answer

  • B

    If, after performing exactly relaxation iterations, an additional relaxation of any edge further reduces a distance value, then a negative-weight cycle is present.

See the whole paperTake it as a mock test

Question 2 of 16 in the IIT Madras BS Programming in Python (Python) Quiz 2 paper sat on 12 Apr 2026, in the January 2026 term (Programming, Data Structures And Algorithms Using Python 06 Apr 26). It carries 3 marks.

This question was also asked in

More questions from this paper

  1. Q1Which of the following statements is/are correct about Dijkstra's algorithm to find the shortest path? I. The shortest …
  2. Q3Which of the following correctly represents the final max-heap after inserting elements 1, 2, 3, 5, 7, 6, and 4 in the …
  3. Q4The maximum and minimum number of nodes possible in a binary search tree of height 8 are _. Assume that the height of a…
  4. Q5Consider a Binary Search Tree (BST) containing distinct keys. Each node of the BST is defined using the following class…
  5. Q6Suppose the letters {a, b, c, d, e} occur with the following frequencies. How many bits will be used to encode the lett…
  6. Q7Consider a set of activities , where each activity has: • a processing time (time required to complete the activity), a…
  7. Q8In a list , two elements and form a significant inversion if The total number of significant inversions for is _.
  8. Q9Consider the Quick Select algorithm for finding the smallest element in an input list of size containing distinct eleme…
  9. Q10Consider the following strategy to solve a problem of input size . Divide the problem into sub-problems, each of size ,…
  10. Q11Let be a connected complete graph with 4 vertices and 6 edges, where all edge weights are distinct and ordered as: Whic…
  11. Q12Consider a min-heap implemented using an array with distinct elements. Which of the following statements about the time…
  12. Q13Consider the given weighted adjacency matrix for a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Where in …
  13. Q14In the table below, we have 9 activities with the corresponding start and finish times. It might not be possible to com…
  14. Q15An AVL tree contains 120 nodes. What is the maximum possible height of the AVL tree? Assume that the height of an empty…
  15. Q16Consider the following function What median value will be returned by the given function for the following list?