Greedy-approach
October 26, 2023TIFR PHD 2022
October 26, 2023Greedy-approach
| Question 11 |
Which of the following algorithms is fastest to find shortest path from a source node to a destination node in an un-weighted connected graph?
| Warshall’s algorithm | |
| Floyd’s algorithm | |
| Breadth First Traversal | |
| Depth First Traversal |
Question 11 Explanation:
warshall algorithm will take O(n^3) time.
Floyd’s algorithm will take O(n^3) time.
Breadth First traversal will take O(m+n) time.
Depth first traversal will work only if the graph is tree.
Hence among the given options Breadth first traversal is best.
Floyd’s algorithm will take O(n^3) time.
Breadth First traversal will take O(m+n) time.
Depth first traversal will work only if the graph is tree.
Hence among the given options Breadth first traversal is best.
Correct Answer: C
Question 11 Explanation:
warshall algorithm will take O(n^3) time.
Floyd’s algorithm will take O(n^3) time.
Breadth First traversal will take O(m+n) time.
Depth first traversal will work only if the graph is tree.
Hence among the given options Breadth first traversal is best.
Floyd’s algorithm will take O(n^3) time.
Breadth First traversal will take O(m+n) time.
Depth first traversal will work only if the graph is tree.
Hence among the given options Breadth first traversal is best.