Question 5633 – NIELIT Technical Assistant_2016_march
December 13, 2023Web-Technologies
December 13, 2023Question 11051 – Algorithms
In the following table, the left column contains the names of standard graph algorithms and the right column contains the time complexities of the algorithms. Match each algorithm with its time complexity.
1. Bellman-Ford algorithm A: O ( m log n) 2. Kruskal’s algorithm B: O (n3) 3. Floyd-Warshall algorithm C: O (nm) 4. Topological sorting D: O (n + m)
Correct Answer: A
Question 46 Explanation:
Bellman-ford algorithm → O(nm)
Krushkal’s algorithm → O(m log n)
Floyd-Warshall algorithm → O(n3)
Topological sorting → O(n+m)
Krushkal’s algorithm → O(m log n)
Floyd-Warshall algorithm → O(n3)
Topological sorting → O(n+m)
1→ C, 2 → A, 3 → B, 4 → D
1→ B, 2 → D, 3 → C, 4 → A
1→ C, 2 → D, 3 → A, 4 → B
1→ B, 2 → A, 3 → C, 4 → D