Topic: Algorithms
Match the following table showing algorithm and its application.
(P) A person wants to visit from one place to another place in shortest period
(Q) A person wants to visit M places in shortest period
(R) All N persons wants to visit all M places in shortest period
(i) Floyd's algorithm
(ii) Multi-stage graph algorithm
(iii) Dijkstra's algorithm
- A. P-(ii), Q - (iii), R- (i)
- B. P-(i), Q - (iii), R - (ii)
- C. P-(ii), Q- (i), R - (iii)
- D. P-(i), Q- (ii), R- (iii)
Answer: A. P-(ii), Q - (iii), R- (i)
Explanation: Based on the types of shortest path problems:
- (P) 'From one place to another place' maps best to finding a path from a single source to a single destination through stages, which is effectively solved by a Multi-stage graph algorithm (ii).
- (Q) 'Visit M places from a source' represents finding shortest paths from a single source to all other nodes (M places), which maps to Dijkstra's algorithm (iii).
- (R) 'All N persons want to visit all M places' represents finding the shortest path between all pairs of vertices in a graph, which maps to Floyd-Warshall algorithm (i).