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

Updated 11 Nov 20265 min read
Floyd-Warshall and Subset Sum: Dynamic Programming Tables, Worked Examples and Exam Traps

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 k

min(D^(k-1)[i][j], D^(k-1)[i][k] + D^(k-1)[k][j])

Minimum distance

Subset sum

Item i

dp[i-1][s] OR dp[i-1][s-a_i], when s >= a_i

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.

Code
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

D^(0)

[0,3,INF,7] [8,0,2,INF] [5,INF,0,1] [2,INF,INF,0]

After A

[0,3,INF,7] [8,0,2,15] [5,8,0,1] [2,5,INF,0]

After B

[0,3,5,7] [8,0,2,15] [5,8,0,1] [2,5,7,0]

After C

[0,3,5,6] [7,0,2,3] [5,8,0,1] [2,5,7,0]

After D

[0,3,5,6] [5,0,2,3] [3,6,0,1] [2,5,7,0]

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.

Two-panel Floyd-Warshall figure shows a weighted graph and distance matrices, including A to C improving from infinity to 5 and B to A from 8 to 5.

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

3

T

F

F

T

F

F

F

F

F

F

3,4

T

F

F

T

T

F

F

T

F

F

3,4,5

T

F

F

T

T

T

F

T

T

T

3,4,5,2

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.

Boolean subset-sum grid for items 3, 4, 5, and 2 with target 9 shows the recovered subset {4,5} and the check 4+5=9.

6. Floyd-Warshall and Subset Sum traps: invariants, reconstruction and boundaries

Trap

Fix

Put i or j outside k

Keep the admitted-intermediate loop k outermost.

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 D[i][i]<0 warns of a reachable negative cycle and invalidates ordinary shortest-path meaning for affected pairs.

Read row i on subset sum's take branch

Read row i-1, or scan a 1D array downward.

Leave sum 0 false

Initialise it true so later sums have a base.

Collapse duplicate values

Treat occurrences as separate items. [3,3] can form 6.

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:

  1. Define the state boundary.

  2. Write the avoid-or-use recurrence.

  3. Keep the boundary loop outermost.

  4. Initialise the base row or matrix correctly.

  5. 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.