Question 1 The time complexity of the Bellman-Ford algorithm as outlined in the article is:...
Palo Alto Networks technical mcq question, verified with a worked answer. Free to practise - no sign-up.
The time complexity of the Bellman-Ford algorithm as outlined in the article is:
Select any one of the following options
Show answer & explanation
Answer: B. B) O(V*E)\n
The Bellman-Ford algorithm relaxes all |E| edges for |V|-1 iterations, yielding an overall time complexity of O(V * E).
Step-by-step Derivation:
Step 1: Bellman-Ford computes single-source shortest paths in graphs with possible negative edge weights.
Step 2: It runs |V|-1 relaxation phases, and in each phase, it iterates through all |E| edges.
Step 3: Overall time complexity = (|V|-1) * |E| = O(V * E).