Match the following table showing algorithm and its application. Scenarios…
2025
Match the following table showing algorithm and its application.
Scenarios | Algorithms |
(P) A person wants to visit from one place to another place in shortest period | (i) Floyd's algorithm |
(Q) A person wants to visit M places in shortest period | (ii) Multi-stage graph algorithm |
(R) All N persons wants to visit all M places in shortest period | (iii) Dijkstra's algorithm |
Answer: D. P – (i), Q – (ii), R – (iii) — ConceptShortest-path algorithms are distinguished by the query model and graph structure. Floyd–Warshall precomputes all-pairs distances, Dijkstra handles…
- A.
P – (iii), Q – (ii), R – (i)
- B.
P – (i), Q – (iii), R – (ii)
- C.
P – (ii), Q – (i), R – (iii)
- D.
P – (i), Q – (ii), R – (iii)
Attempted by 437 students.
Show answer & explanation
Correct answer: D
Concept
Shortest-path algorithms are distinguished by the query model and graph structure. Floyd–Warshall precomputes all-pairs distances, Dijkstra handles non-negative weighted single-source queries and can be repeated for several sources, and the multi-stage graph method uses the layered structure of a directed acyclic graph.
A matching question must therefore be read using the particular operational interpretation adopted by its source examination.
Application
For P, the official ISRO interpretation uses Floyd’s algorithm: an all-pairs distance table can answer a requested place-to-place query.
For Q, the visit through M places is interpreted as movement through successive stages, so it is paired with the multi-stage graph algorithm.
For R, Dijkstra’s algorithm is interpreted as being run from each relevant person’s starting vertex to obtain routes to the M destinations, assuming non-negative edge weights.
Cross-check
The revised final ISRO Computer Science answer key for the 2025 A-series Question 37 selects the mapping P–(i), Q–(ii), R–(iii).
The wording is not algorithmically exclusive: Dijkstra can also answer a single source-to-destination query, while Floyd–Warshall is the direct all-pairs method. The accepted mapping here follows the official PYQ key rather than claiming those alternatives are impossible.
Therefore, the officially accepted matching is P–(i), Q–(ii), R–(iii).