Floyd-Warshall and Subset Sum: Dynamic Programming Tables, Worked Examples and Exam Traps
Trace a four-vertex Floyd-Warshall matrix and a complete subset-sum table for target 9. Learn the state boundaries, loop order, reconstruction steps and common traps.
KnowledgeGate Team
Exam prep & CS education

Floyd-Warshall and subset sum look unrelated: one fills a graph distance matrix, while the other fills a Boolean table for a target sum. Yet both use dynamic programming over ordered choices. A four-vertex all-pairs matrix and a subset-sum table for [3, 4, 5, 2] with target 9 demonstrate each recurrence, loop order, answer reconstruction and common traps.
1. Floyd-Warshall and Subset Sum: one DP pattern, two state spaces
Dynamic programming reuses overlapping subproblem answers inside a state boundary. D^(k)[i][j] is the shortest i to j path whose internal vertices come only from the first k vertices. dp[i][s] says whether the first i items can form s. The superscript or row is a permission boundary.
Algorithm | Newly allowed choice | Recurrence | Stored answer |
|---|---|---|---|
Floyd-Warshall | Vertex |
| Minimum distance |
Subset sum | Item |
| Boolean reachability |
Floyd-Warshall handles directed or undirected weighted graphs and negative edges, but an ordinary shortest path is undefined for source-target pairs affected by a reachable negative cycle. This subset-sum table assumes non-negative integers. The GATE CS Exam Preparation category places both techniques beside their prerequisite algorithms and complexity analysis.
2. Floyd-Warshall recurrence: admit one intermediate vertex at a time
Set D^(0)[i][i]=0, direct edges to w(i,j), and other cells to infinity. Then apply:
D^(k)[i][j] = min(D^(k-1)[i][j], D^(k-1)[i][k] + D^(k-1)[k][j])
The path either avoids k or travels through it.
for k = 1 to V:
for i = 1 to V:
for j = 1 to V:
if D[i][k] and D[k][j] are finite:
D[i][j] = min(D[i][j], D[i][k] + D[k][j])Keep k outermost; swapping it with i or j breaks the boundary. In-place updates give O(V^3) time and O(V^2) space. A reconstruction matrix adds O(V^2). Check both legs before addition because an infinity sentinel may overflow.
3. Floyd-Warshall worked example: trace all four intermediate vertices
Use order A, B, C, D: A->B=3, A->D=7, B->A=8, B->C=2, C->A=5, C->D=1, D->A=2. Other edges are infinity.
Boundary | Matrix rows in order A, B, C, D |
|---|---|
|
|
After |
|
After |
|
After |
|
After |
|
After A, C->B=min(INF,5+3)=8 and D->B=min(INF,2+3)=5. After B, A->C=min(INF,3+2)=5 and D->C=min(INF,5+2)=7. After C, A->D=min(7,5+1)=6, B->A=min(8,2+5)=7, B->D=min(15,2+1)=3. After D, B->A=min(7,3+2)=5, C->A=min(5,1+2)=3, C->B=min(8,1+5)=6.
Verify: A->B->C->D costs 3+2+1=6, B->C->D->A costs 2+1+2=5, and C->D->A->B costs 1+2+3=6. Graph MCQs: 10 Solved BFS, DFS, Connectivity (GATE) supports graph practice, but BFS and DFS do not compute weighted all-pairs distances.

4. Subset Sum recurrence: skip an item or take it once
dp[i][s] is true when some subset of the first i items sums to s. Set dp[0][0]=true and other base cells false. For a_i:
dp[i][s] = dp[i-1][s] OR (s >= a_i AND dp[i-1][s-a_i])
Both branches read row i-1, so item i is used at most once. The full table costs O(nT) time and space. One-dimensional storage costs O(T), but sums must run downward; an upward scan may reuse the current item and solve an unbounded variant.
It is pseudo-polynomial because runtime depends on numeric T, not only its bit length. Negative items need another state design.
5. Subset Sum worked example: fill the table for target 9 and recover a subset
For [3,4,5,2], each row uses only admitted items.
Items allowed | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
None | T | F | F | F | F | F | F | F | F | F |
| T | F | F | T | F | F | F | F | F | F |
| T | F | F | T | T | F | F | T | F | F |
| T | F | F | T | T | T | F | T | T | T |
| T | F | T | T | T | T | T | T | T | T |
Check the boundary: dp[2][7]=dp[1][7] OR dp[1][3]=F OR T=T, using 3+4. dp[3][6]=dp[2][6] OR dp[2][1]=F OR F=F. dp[3][9]=dp[2][9] OR dp[2][4]=F OR T=T, using 4+5.
Backtrack by skipping item i when dp[i-1][s] is true. From dp[4][9], skip 2; take 5 because dp[2][9] is false and dp[2][4] true; then take 4. This gives {4,5}, with 4+5=9. {3,4,2} also works, so witnesses need not be unique. The earlier Backtracking Technique: Concepts, Two Worked Examples and Exam Patterns uses the same [3,4,5,2] input to expose include/exclude DFS and pruning. Here, the identical input isolates the DP difference: reusable (item count, sum) states replace a search path, and the table records every reachable sum up to 9.

6. Floyd-Warshall and Subset Sum traps: invariants, reconstruction and boundaries
Trap | Fix |
|---|---|
Put | Keep the admitted-intermediate loop |
Add an infinity sentinel | Check both path legs are finite first. |
Confuse Floyd-Warshall with Boolean Warshall | Floyd uses min-plus distances; Boolean Warshall tests reachability. |
Reject every negative edge | Allow negative edges. A final |
Read row | Read row |
Leave sum | Initialise it true so later sums have a base. |
Collapse duplicate values | Treat occurrences as separate items. |
Floyd routes need a next-hop or predecessor matrix. Subset-sum witnesses come from earlier rows. A 1D array needs extra bookkeeping or recomputation.
7. Floyd-Warshall and Subset Sum exam patterns: what to calculate under pressure
Questions may ask for a Floyd entry, recurrence, loop order, complexity, negative-cycle test, subset-sum row, witness, or 0/1 versus unbounded code. Classify the required output before calculating, because each form tests a different state boundary.
Six quick checks: after A and B, D->C=7 from 5+2; after C, B->D=3 from 2+1; finally, C->B=6 from 1+2+3. With 3,4, sum 7 is true. With 3,4,5, sum 6 is false because both recurrence branches are false. With all items, 9 is true.
Recognition checklist: minimum through an admitted vertex means Floyd-Warshall; Boolean take-or-skip means subset sum; downward iteration means 0/1 use; a negative diagonal warns of a negative cycle. Use the GATE Test Series to practise these forms, then record whether each error came from the state, recurrence, boundary, or reconstruction.
8. Floyd-Warshall and Subset Sum: the short version and next step
Recall these five points:
Define the state boundary.
Write the avoid-or-use recurrence.
Keep the boundary loop outermost.
Initialise the base row or matrix correctly.
Reconstruct separately from the stored optimum or decision.
Checkpoints: Floyd's final B row is [5,0,2,3]; subset sum is true for 9 with {4,5}. If A->D becomes 4, it stays 4 because min(4,3+2+1)=4. Target 6 is true through {4,2}, although false before 2 arrived.
Use GATE Guidance by Sanchit Sir for a structured route through Algorithms and wider GATE CS. For immediate revision, redraw both diagrams, reproduce Floyd's row for B, and backtrack {4,5} from 9.
Keep learning
Floyd-Warshall and Subset Sum Interview Questions: 10 Worked Answers
Prepare two classic dynamic programming problems through ten interview-style questions, complete traces, follow-up answers and quick checks for common mistakes.
Floyd-Warshall & Subset Sum MCQs: 12 Solved Questions with Explanations
Solve 12 Floyd-Warshall and Subset Sum questions with concise explanations and worked DP examples.
Shortest Path Algorithms: Dijkstra, Bellman-Ford and Floyd-Warshall with Worked Examples for GATE CS
Learn the relaxation idea behind shortest paths, trace three core algorithms by hand, and choose the right method from edge weights and source count.
Backtracking Technique MCQs: Solved PYQs on N-Queens, Hamiltonian Cycle and Subset Sum
Attempt seven previous-year Backtracking Technique MCQs before checking the solutions. Then revise five descriptive questions with compact model-answer frameworks.





