Bellman-Ford Algorithm Multiple Choice Questions and Answers (MCQs)

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Bellman-Ford Algorithm”.

1. The Bellmann Ford algorithm returns _______ value.
a) Boolean
b) Integer
c) String
d) Double
View Answer

Answer: a
Explanation: The Bellmann Ford algorithm returns Boolean value whether there is a negative weight cycle that is reachable from the source.

2. Bellmann ford algorithm provides solution for ____________ problems.
a) All pair shortest path
b) Sorting
c) Network flow
d) Single source shortest path
View Answer

Answer: d
Explanation: Bellmann ford algorithm is used for finding solutions for single source shortest path problems. If the graph has no negative cycles that are reachable from the source then the algorithm produces the shortest paths and their weights.

3. Bellmann Ford algorithm is used to indicate whether the graph has negative weight cycles or not.
a) True
b) False
View Answer

Answer: a
Explanation: Bellmann Ford algorithm returns true if the graph does not have any negative weight cycles and returns false when the graph has negative weight cycles.
advertisement
advertisement

4. How many solution/solutions are available for a graph having negative weight cycle?
a) One solution
b) Two solutions
c) No solution
d) Infinite solutions
View Answer

Answer: c
Explanation: If the graph has any negative weight cycle then the algorithm indicates that no solution exists for that graph.

5. What is the running time of Bellmann Ford Algorithm?
a) O(V)
b) O(V2)
c) O(ElogV)
d) O(VE)
View Answer

Answer: d
Explanation: Bellmann Ford algorithm runs in time O(VE), since the initialization takes O(V) for each of V-1 passes and the for loop in the algorithm takes O(E) time. Hence the total time taken by the algorithm is O(VE).
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

6. How many times the for loop in the Bellmann Ford Algorithm gets executed?
a) V times
b) V-1
c) E
d) E-1
View Answer

Answer: b
Explanation: The for loop in the Bellmann Ford Algorithm gets executed for V-1 times. After making V-1 passes, the algorithm checks for a negative weight cycle and returns appropriate boolean value.

7. Dijikstra’s Algorithm is more efficient than Bellmann Ford Algorithm.
a) True
b) False
View Answer

Answer: a
Explanation: The running time of Bellmann Ford Algorithm is O(VE) whereas Dijikstra’s Algorithm has running time of only O(V2).
advertisement

8. Identify the correct Bellmann Ford Algorithm.
a)

for i=1 to V[g]-1
	do for each edge (u,v) in E[g]
		do Relax(u,v,w)
   for each edge (u,v) in E[g]
	do if d[v]>d[u]+w(u,v)
		then return False
   return True

b)

advertisement
for i=1 to V[g]-1
       for each edge (u,v) in E[g]
	do if d[v]>d[u]+w(u,v)
		then return False
    return True

c)

for i=1 to V[g]-1
	do for each edge (u,v) in E[g]
		do Relax(u,v,w)
   for each edge (u,v) in E[g]
	do if d[v]<d[u]+w(u,v)
		then return true
   return True

d)

for i=1 to V[g]-1
	do for each edge (u,v) in E[g]
		do Relax(u,v,w)
   return True
View Answer
Answer: a
Explanation: After initialization, the algorithm makes v-1 passes over the edges of the graph. Each pass is one iteration of the for loop and consists of relaxing each edge of the graph once. Then it checks for the negative weight cycle and returns an appropriate Boolean value.
 
 

9. What is the basic principle behind Bellmann Ford Algorithm?
a) Interpolation
b) Extrapolation
c) Regression
d) Relaxation
View Answer

Answer: d
Explanation: Relaxation methods which are also called as iterative methods in which an approximation to the correct distance is replaced progressively by more accurate values till an optimum solution is found.

10. Bellmann Ford Algorithm can be applied for _____________
a) Undirected and weighted graphs
b) Undirected and unweighted graphs
c) Directed and weighted graphs
d) All directed graphs
View Answer

Answer: c
Explanation: Bellmann Ford Algorithm can be applied for all directed and weighted graphs. The weight function in the graph may either be positive or negative.

11. Bellmann Ford algorithm was first proposed by ________
a) Richard Bellmann
b) Alfonso Shimbe
c) Lester Ford Jr
d) Edward F. Moore
View Answer

Answer: b
Explanation: Alfonso Shimbe proposed Bellmann Ford algorithm in the year 1955. Later it was published by Richard Bellmann in 1957 and Lester Ford Jr in the year 1956. Hence it is called Bellmann Ford Algorithm.

12. Consider the following graph. What is the minimum cost to travel from node A to node C?
The minimum cost to travel from node A to node C is 2 in given graph
a) 5
b) 2
c) 1
d) 3
View Answer

Answer: b
Explanation: The minimum cost to travel from node A to node C is 2.
A-D, cost=1
D-B, cost=-2
B-C, cost=3
Hence the total cost is 2.

13. In the given graph, identify the path that has minimum cost to travel from node a to node f.
a-d-b-c-e-f is the path that has minimum cost to travel from node a to node f in graph
a) a-b-c-f
b) a-d-e-f
c) a-d-b-c-f
d) a-d-b-c-e-f
View Answer

Answer: d
Explanation: The minimum cost taken by the path a-d-b-c-e-f is 4.
a-d, cost=2
d-b, cost=-2
b-c, cost=1
c-e, cost= 2
e-f, cost=1
Hence the total cost is 4.

14. Bellmann Ford Algorithm is an example for ____________
a) Dynamic Programming
b) Greedy Algorithms
c) Linear Programming
d) Branch and Bound
View Answer

Answer: a
Explanation: In Bellmann Ford Algorithm the shortest paths are calculated in bottom up manner which is similar to other dynamic programming problems.

15. A graph is said to have a negative weight cycle when?
a) The graph has 1 negative weighted edge
b) The graph has a cycle
c) The total weight of the graph is negative
d) The graph has 1 or more negative weighted edges
View Answer

Answer: c
Explanation: When the total weight of the graph sums up to a negative number then the graph is said to have a negative weight cycle. Bellmann Ford Algorithm provides no solution for such graphs.

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.