All-pairs shortest paths: Floyd–Warshall

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Bellman–Ford cost? from Lesson 6.3.2
• Matrix-chain time? from Lesson 5.2.1
• Dijkstra needs which weights? from Lesson 6.3.1

1 · The Hook

🎣

A distance table on a road atlas lists the shortest distance between every pair of cities. Running Dijkstra from each vertex is one way; Floyd–Warshall does it with a triple loop and a DP so simple that GATE asks you to trace it by hand.

2 · Predict First

🤔

Directed graph on 1–4: 1→2 3, 1→4 7, 2→1 8, 2→3 2, 3→1 5, 3→4 1, 4→1 2. Shortest distance from 2 to 4?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

2 → 3 → 4 = 2 + 1 = 3.

Recurrence

D⁽ᵏ⁾[i][j] = shortest i → j path whose intermediate vertices all lie in {1, …, k}.

• D⁽⁰⁾ = the weight matrix (0 on the diagonal, ∞ where there is no edge).
• D⁽ᵏ⁾[i][j] = min( D⁽ᵏ⁻¹⁾[i][j], D⁽ᵏ⁻¹⁾[i][k] + D⁽ᵏ⁻¹⁾[k][j] ).

for k = 1 to V:            // k must be the OUTER loop
    for i = 1 to V:
        for j = 1 to V:
            D[i][j] = min(D[i][j], D[i][k] + D[k][j])

Θ(V³) time, Θ(V²) space (one matrix, updated in place). Works with negative edges; a negative cycle shows up as D[i][i] < 0.

Trace for the predict graph

Final matrix:

Relatives

• Warshall's transitive closure: same loops with "or/and" on booleans: is j reachable from i? Θ(V³).
• All-pairs alternatives: V × Dijkstra = O(V(V + E) log V) (non-negative weights), V × Bellman–Ford = O(V²E).

4 · Visual

D[i][j] = min( D[i][j] , D[i][k] + D[k][j] )

        i ---------------------> j        (best so far, intermediates < k)
         \                     /
          \--> k ------------>/           (go through k)

5 · Worked Examples

Example 1 Easy

In the final matrix, shortest distance from 3 to 2?

Solution

3 → 4 → 1 → 2 = 1 + 2 + 3 = 6 (via the direct 3 → 1 edge it would be 8).

Example 2 Medium

Floyd–Warshall on 100 vertices: how many executions of the innermost min?

Solution

100³ = 1,000,000.

Example 3 GATE

After the k = 2 pass (intermediates in {1, 2}), what is D[1][3]?

Solution

1 → 2 → 3 = 3 + 2 = 5.

6 · GATE Traps

⚠️

• k is the outermost loop; swapping the loop order breaks the algorithm.
• D⁽ᵏ⁾ allows intermediates up to k, not paths of k edges.
• Negative edges are fine; a negative cycle shows as a negative diagonal entry.
• Θ(V³) regardless of E.

7 · Memory Hook

🧠

"Let k in as a stopover, for every pair."

8 · Connect the Dots

Phase 6 is complete, and with it every topic on the GATE Algorithms syllabus. Phase 7 pulls it together: a rule sheet, mixed practice, a pattern drill and the final test.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markFloyd

In the lesson's final matrix, D[2][1]?

Numerical answer: ________

Q2NAT2 marksFloyd pass

After the k = 1 pass, what is D[2][4]?

Numerical answer: ________

Q3NAT2 marksFloyd

In the final matrix, D[1][4]?

Numerical answer: ________

Q4MCQ1 markCost

Floyd–Warshall on V vertices runs in:

• (A) Θ(V² log V)
• (B) Θ(V³)
• (C) Θ(V²)
• (D) Θ(VE)

Q5MSQ2 marksFacts

Which are true about Floyd–Warshall?

• (A) It needs only Θ(V²) space.
• (B) The loop over k may be placed innermost.
• (C) A negative cycle makes some D[i][i] negative.
• (D) It works with negative edge weights.

10 · Rule Card

• D⁽ᵏ⁾[i][j] = min(D⁽ᵏ⁻¹⁾[i][j], D⁽ᵏ⁻¹⁾[i][k] + D⁽ᵏ⁻¹⁾[k][j]); k outermost.
• Θ(V³) time, Θ(V²) space; negatives OK; negative cycle ⇔ D[i][i] < 0.
• Transitive closure: same loops on booleans.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

all-pairs shortest pathsFloyd–Warshallintermediate-vertex DPk outermostnegative diagonalWarshall's transitive closure

12 · Answer Vault