The Floyd-Warshall algorithm for all-pair shortest paths computation is based on (A) Greedy paradigm. (B) Divide-and-Conquer paradigm. (C) Dynamic Programming paradigm. (D) neither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm.

Select one answerSingle correct

Pick an option to check

Solution

Step-by-step verified solution

Official answer: C) Dynamic Programming paradigm.

Dynamic Programming

The Floyd-Warshall algorithm is a classic Dynamic Programming algorithm used to compute all-pairs shortest paths in a weighted directed graph.

It defines the subproblem $D^{(k)}[i][j]$ as the shortest path from vertex $i$ to vertex $j$ using only intermediate vertices from the set $\{1, 2, \dots, k\}$ , with the recurrence relation:

D^{(k)}[i][j] = \min\left(D^{(k-1)}[i][j],\; D^{(k-1)}[i][k] + D^{(k-1)}[k][j]\right)

Hence, the correct option is (C).

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

This Dynamic Programming previous year question is Q14 of the GATE CSE 2016 Set 2 paper. Find more GATE CSE PYQs on Dynamic Programming in Algorithms, or browse all GATE CSE PYQs.

Free diagnostic

Where do you stand for GATE?

Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Dynamic Programming PYQs now with no account.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Dynamic Programming in GATE CSE

Dynamic Programming has 7 GATE CSE PYQs across 6 papers from 2011 to 2026. 2 of them are 1-mark MCQs like this one, and GATE CSE 2016 Set 2 has 2.

How GATE tests Dynamic Programming

More from GATE CSE 2016 Set 2

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.