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

  1. A.

    P – (iii), Q – (ii), R – (i)

  2. B.

    P – (i), Q – (iii), R – (ii)

  3. C.

    P – (ii), Q – (i), R – (iii)

  4. D.

    P – (i), Q – (ii), R – (iii)

Attempted by 158 students.

Show answer & explanation

Correct answer: A

To determine the correct matching, we analyze the graph theory problem associated with each scenario.

Scenario R describes all persons visiting all places, which is the All-Pairs Shortest Path problem. Floyd's algorithm (i) is specifically designed for this.

Scenario P involves traveling from one place to another, representing a Single-Source Shortest Path problem. Dijkstra's algorithm (iii) is the standard solution for this.

Scenario Q involves visiting multiple places in the shortest period, which aligns with optimization through stages. This matches the Multi-stage graph algorithm (ii).

Thus, the correct matching is P with (iii), Q with (ii), and R with (i).

Explore the full course: Isro