Floyd-Warshall and Subset Sum recur across GATE, UGC NET, ISRO and PSU papers, and they get mixed up because both answer to the name dynamic programming. Floyd-Warshall relaxes an all-pairs distance matrix over n candidate intermediate vertices; Subset Sum fills a Boolean table recording which totals the first i values can reach. Attempt each question before reading its answer, and keep Dynamic Programming Explained: 0/1 Knapsack open if the DP table itself is unclear.
1. Floyd-Warshall fundamentals
Floyd-Warshall finds all-pairs shortest paths by letting one vertex at a time act as an intermediate, so after the k-th pass every d[i][j] is the shortest route that uses only vertices 1 to k as stopovers. Graph Algorithms: BFS, DFS and Dijkstra Traced Step by Step contrasts the single-source methods.
Q1 (GATE 2016)
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.
Answer: (C). The path through {1, ..., k} reuses paths through {1, ..., k - 1}: optimal substructure plus overlapping subproblems. Greedy commits locally; divide-and-conquer needs independent subproblems. (see the solved page)
Q2 (UPPSC Polytechnic Lecturer 2018)
Which of the following algorithms solves the all-pairs shortest path problem?
(A) Dijkstra's algorithm
(B) Floyd's algorithm
(C) Prim's algorithm
(D) Warshall's algorithm.
Answer: (B). Floyd finds weighted every-pair distances; Warshall finds unweighted reachability. Dijkstra is single-source, while Prim builds a minimum spanning tree. (see the solved page)
Q3 (UGC NET 2015)
Floyd-Warshall algorithm utilizes _____ to solve the all-pairs shortest paths problem on a directed graph in ____ time.
(A) Greedy algorithm, Θ(V³)
(B) Greedy algorithm, Θ(V² lg n)
(C) Dynamic programming, Θ(V³)
(D) Dynamic programming, Θ(V² lg n).
Answer: (C). Dynamic programming uses nested k, i and j loops. Each spans V vertices, giving Θ(V³). (see the solved page)
2. Floyd-Warshall complexity
The bound does not move with the input: the same n³ cell updates run on a dense graph and on one with three edges.
Q4 (LTI Mindtree 2023)
What is the time complexity of the Floyd-Warshall algorithm to calculate all the shortest paths of a pair in an n-vertex graph?
(A) O(n²logn)
(B) Θ(n²logn)
(C) Θ(n⁴)
(D) Θ(n³).
Answer: (D). The k-loop runs n times. Each pass sweeps an n by n table, totalling Θ(n³). (see the solved page)
Q5 (Coal India 2017)
Which of the following is the best-case time complexity of Floyd's algorithm for finding shortest paths in a graph with 'n' vertices?
(A) Θ(n²)
(B) Θ(1)
(C) Θ(n)
(D) Θ(n³).
Answer: (D). Floyd-Warshall has no early exit. Its triple loop always completes, so best and worst cases are Θ(n³). (see the solved page)
Q6 (GATE 2005)
The time complexity of computing the transitive closure of a binary relation on a set of n elements is known to be
(A) O(n)
(B) O(n log n)
(C) O(n^(3/2))
(D) O(n³).
Answer: (D). Transitive closure is Warshall's problem, and Warshall reuses Floyd's triple-loop shape with Boolean OR and AND in place of minimum and addition. Swapping the operators does not change the loop count, so the time stays O(n³). (see the solved page)
3. Harder Floyd-shaped questions
Both of these change one operator in the Floyd update and then ask what the matrix means. Q7 swaps minimum for maximum; Q8 asks how heavy an edge can get and still sit on a shortest path.
Q7 (GATE 2003)
Let G(V, E) be a directed graph with n vertices. A path from vi to vj in G is a sequence of vertices (vi, vi+1, ..., vj) such that (vk, vk+1) ∈ E for all k in i through j-1. A simple path is a path in which no vertex appears more than once. Let A be an n x n array initialized as follows: A[j, k] = 1 if (j, k) ∈ E, and 0 otherwise. Consider the algorithm: for i = 1 to n; for j = 1 to n; for k = 1 to n; A[j, k] = max(A[j, k], A[j, i] + A[i, k]). Which of the following statements is necessarily true for all j and k after termination of the above algorithm?
(A) A[j, k] ≤ n
(B) If A[j, k] ≥ n - 1, then G has a Hamiltonian cycle
(C) If there exists a path from j to k, A[j, k] contains the longest path length from j to k
(D) If there exists a path from j to k, every simple path from j to k contains at most A[j, k] edges.
Answer: (D). With maximum and addition, the recurrence assembles every simple path, so A[j, k] upper-bounds its edge count. Shared vertices defeat exactness. Cycles can push A[j, k] beyond n. (see the solved page)
Q8 (GATE 2016, NAT)
Consider the weighted undirected graph with 4 vertices, where the weight of edge {i, j} is given by the entry Wij in the matrix W:
1 | 2 | 3 | 4 | |
|---|---|---|---|---|
1 | 0 | 2 | 8 | 5 |
2 | 2 | 0 | 5 | 8 |
3 | 8 | 5 | 0 | x |
4 | 5 | 8 | x | 0 |
The largest possible integer value of x, for which at least one shortest path between some pair of vertices will contain the edge with weight x, is ___.
Answer: 12. The best x-free 3-to-4 route is 3-2-1-4: 5 + 2 + 5 = 12; both two-edge alternatives cost 13. Thus x ≤ 12, with the direct edge tying at 12. Other pairs add positive edges, so {3, 4} is binding. (see the solved page)
4. Subset Sum problem and recurrence
Subset Sum asks whether some subset hits K exactly. Its Boolean DP records whether the first i values form j.
Q9 (ISRO 2018)
The following paradigm can be used to find the solution of the problem in minimum time: Given a set of non-negative integers, and a value K, determine if there is a subset of the given set with sum equal to K:
(A) Divide and Conquer
(B) Dynamic Programming
(C) Greedy Algorithm
(D) Branch and Bound.
Answer: (B). Subproblems asking whether the first i elements make j overlap, giving O(nK) DP. Greedy may leave an impossible remainder. (see the solved page)
Q10 (GATE 2008)
The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1, a2, a3, ..., an} and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array X, with n rows and W+1 columns. X[i, j], 1 <= i <= n, 0 <= j <= W, is TRUE if and only if there is a subset of {a1, a2, ..., ai} whose elements sum to j. Which of the following is valid for 2 <= i <= n and ai <= j <= W?
(A) X[i, j] = X[i - 1, j] ∨ X[i, j - ai]
(B) X[i, j] = X[i - 1, j] ∨ X[i - 1, j - ai]
(C) X[i, j] = X[i - 1, j] ∧ X[i, j - ai]
(D) X[i, j] = X[i - 1, j] ∧ X[i - 1, j - ai].
Answer: (B). Omit ai for X[i - 1, j], or use it once for X[i - 1, j - ai]; OR accepts either route. Option (A) uses the current row and can reuse ai like coin change. (see the solved page)
5. Subset Sum table and pseudo-polynomial time
The last two questions read the finished table: which cell holds the verdict, and what O(nW) is actually worth once you count the bits it takes to write W.
Q11 (GATE 2008)
Using the setup from Q10, which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W?
(A) X[1, W]
(B) X[n, 0]
(C) X[n, W]
(D) X[n-1, n].
Answer: (C). Row n allows every element and column W is the target, so X[n, W] answers the problem. X[n, 0] only records the empty subset. (see the solved page)
Q12 (GATE 2008)
The subset-sum problem is defined as follows: Given a set S of n positive integers and a positive integer W, determine whether there is a subset of S whose elements sum to W. An algorithm Q solves this problem in O(nW) time. Which of the following statements is false?
(A) Q solves the subset-sum problem in polynomial time when the input is encoded in unary
(B) Q solves the subset-sum problem in polynomial time when the input is encoded in binary
(C) The subset sum problem belongs to the class NP
(D) The subset sum problem is NP-hard.
Answer: (B). Binary stores W in Θ(log W) bits, making O(nW) potentially exponential in input length and therefore pseudo-polynomial. Unary makes it polynomial; Subset Sum is in NP and NP-hard, so the other statements hold. (see the solved page)
6. Build both tables yourself
Take an undirected graph with w(1, 2) = 3, w(2, 3) = 4 and w(1, 3) = 10, and apply d[i][j] = min(d[i][j], d[i][k] + d[k][j]) for every k, then every i and j. That triple sweep is where the Θ(n³) comes from.
Only the k = 2 pass changes anything here, because vertex 2 is the one useful stopover: d[1][3] = min(10, d[1][2] + d[2][3]) = min(10, 3 + 4) = 7. The k = 1 and k = 3 passes re-check every pair and find nothing shorter.
After pass | d[1][2] | d[1][3] | d[2][3] |
|---|---|---|---|
Initial weights | 3 | 10 | 4 |
k = 1 | 3 | 10 | 4 |
k = 2 | 3 | 7 | 4 |
k = 3 | 3 | 7 | 4 |
For S = {3, 4, 5}, W = 9, the TRUE columns are:
Row | Values available | TRUE at j |
|---|---|---|
1 | {3} | 0, 3 |
2 | {3, 4} | 0, 3, 4, 7 |
3 | {3, 4, 5} | 0, 3, 4, 5, 7, 8, 9 |
X[3, 9] = X[2, 9] ∨ X[2, 9 - 5] = FALSE ∨ X[2, 4] = TRUE, using {4, 5}; this is Q11's X[n, W].
![Subset Sum DP table for S = {3, 4, 5}, W = 9, with X[3, 9] TRUE reached through the subset {4, 5}.](https://cdn.knowledgegate.ai/blog-assets/blog_asset_1784130226595_ibfxy4.jpg)
7. The short version and next practice
Floyd-Warshall is all-pairs DP and always Θ(n³).
Warshall computes transitive closure in O(n³).
Q7's maximum-plus variant upper-bounds every simple-path length.
Subset Sum uses
X[i - 1, j] ∨ X[i - 1, j - ai]; the answer isX[n, W].O(nW) is pseudo-polynomial when W is encoded in binary.
Work both tables again on paper. The practice page linked from each answer carries about thirty questions on this pair of topics, so there is plenty left to attempt. The GATE Test Series has mocks and topic tests; the Zero to Hero complete CS course covers the full subject.
For the neighbouring graph techniques, work through Graph MCQs: 10 Solved BFS, DFS, Connectivity next.
