Floyd Warshall All Pairs Shortest Path in DSA Typescript

Mental Model

Find the shortest paths between every pair of points by checking if going through a middle point is better than going directly.

Analogy: Imagine you want to find the quickest way to travel between every pair of cities. Sometimes going through a third city is faster than going straight. You check all possible middle cities to find the best routes.

Graph with 4 nodes:
  (0)---5---(1)
   | \       |
   10  3     1
   |     \   |
  (3)---2---(2)

Distance matrix before:
[0, 5, 3, 10]
[∞, 0, 1, ∞]
[∞, ∞, 0, 2]
[∞, ∞, ∞, 0]

Dry Run Walkthrough

Input: Graph with 4 nodes and edges: 0->1=5, 0->3=10, 0->2=3, 1->2=1, 2->3=2; find shortest paths between all pairs

Goal: Calculate shortest distances between every pair of nodes using Floyd Warshall algorithm

Step 1: Initialize distance matrix with direct edges and 0 for self loops

[[0, 5, 3, 10],
 [∞, 0, 1, ∞],
 [∞, ∞, 0, 2],
 [∞, ∞, ∞, 0]]

Why: Start with known direct distances and zero for same node

Step 2: Use node 0 as intermediate to update distances

[[0, 5, 3, 10],
 [∞, 0, 1, ∞],
 [∞, ∞, 0, 2],
 [∞, ∞, ∞, 0]]

Why: No shorter paths found through node 0 yet

Step 3: Use node 1 as intermediate to update distances

[[0, 5, 3, 10],
 [∞, 0, 1, ∞],
 [∞, ∞, 0, 2],
 [∞, ∞, ∞, 0]]

Why: 0->1->2: 5 + 1 = 6 > 3 (direct), so no update. No shorter paths found through node 1.

Step 4: Use node 2 as intermediate to update distances

[[0, 5, 3, 5],
 [∞, 0, 1, 3],
 [∞, ∞, 0, 2],
 [∞, ∞, ∞, 0]]

Why: 0->2->3 is shorter (3 + 2 = 5) than 0->3 direct (10), update 0->3 to 5; 1->2->3 is shorter (1 + 2 = 3) than ∞, update 1->3 to 3

Step 5: Use node 3 as intermediate to update distances

[[0, 5, 3, 5],
 [∞, 0, 1, 3],
 [∞, ∞, 0, 2],
 [∞, ∞, ∞, 0]]

Why: No shorter paths found through node 3

Result:

[[0, 5, 3, 5],
 [∞, 0, 1, 3],
 [∞, ∞, 0, 2],
 [∞, ∞, ∞, 0]]

Annotated Code

DSA Typescript

class FloydWarshall {
  static INF = Number.MAX_SAFE_INTEGER;

  static floydWarshall(graph: number[][]): number[][] {
    const n = graph.length;
    const dist = Array.from({ length: n }, (_, i) =>
      Array.from({ length: n }, (_, j) => graph[i][j])
    );

    for (let k = 0; k < n; k++) {
      for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
          if (dist[i][k] !== FloydWarshall.INF && dist[k][j] !== FloydWarshall.INF) {
            if (dist[i][k] + dist[k][j] < dist[i][j]) {
              dist[i][j] = dist[i][k] + dist[k][j];
            }
          }
        }
      }
    }
    return dist;
  }
}

// Driver code
const INF = FloydWarshall.INF;
const graph = [
  [0, 5, 3, 10],
  [INF, 0, 1, INF],
  [INF, INF, 0, 2],
  [INF, INF, INF, 0],
];

const result = FloydWarshall.floydWarshall(graph);
for (const row of result) {
  console.log(row.map(x => (x === INF ? '∞' : x)).join(' '));
}

for (let k = 0; k < n; k++) {

Use each node as intermediate to check for shorter paths

if (dist[i][k] !== FloydWarshall.INF && dist[k][j] !== FloydWarshall.INF) {

Check if path through k is possible

if (dist[i][k] + dist[k][j] < dist[i][j]) {

Update distance if going through k is shorter

dist[i][j] = dist[i][k] + dist[k][j];

Set new shorter distance

Output

0 5 3 5

∞ 0 1 3

∞ ∞ 0 2

∞ ∞ ∞ 0

Complexity Analysis

Time: O(n^3) because we check all pairs (i, j) for every intermediate node k

Space: O(n^2) because we store distances between all pairs in a matrix

vs Alternative: Compared to running Dijkstra from each node (O(n * (E + V log V))), Floyd Warshall is simpler but slower for sparse graphs

Edge Cases

Graph with no edges except self loops

Distances remain zero on diagonal and infinity elsewhere

DSA Typescript

if (dist[i][k] !== FloydWarshall.INF && dist[k][j] !== FloydWarshall.INF) {

Graph with negative edge weights but no negative cycles

Algorithm correctly finds shortest paths including negative edges

DSA Typescript

if (dist[i][k] + dist[k][j] < dist[i][j]) {

Graph with negative cycle

Algorithm does not detect negative cycles; distances may become incorrect or negative infinity

DSA Typescript

No explicit guard; Floyd Warshall does not handle negative cycle detection here

When to Use This Pattern

When you need shortest paths between all pairs of points and the graph may have negative edges but no negative cycles, use Floyd Warshall to systematically check all intermediate nodes.

Common Mistakes

Mistake: Not checking if intermediate paths exist before adding distances, causing overflow or wrong results
Fix: Add condition to check dist[i][k] and dist[k][j] are not infinity before summing

Mistake: Updating distances without comparing if new path is shorter
Fix: Only update if dist[i][k] + dist[k][j] < dist[i][j]

Summary

Finds shortest paths between all pairs of nodes by considering each node as an intermediate step.

Use when you need all pairs shortest paths and the graph may have negative edges but no negative cycles.

The key insight is that any shortest path can be built by combining shorter paths through intermediate nodes.

Practice

1. What does Floyd-Warshall compute that single-source shortest path algorithms like Dijkstra do not?

easy

A. Shortest path from one source to all vertices

B. Shortest paths between ALL pairs of vertices in one run

C. Minimum spanning tree of the graph

D. Topological order of vertices

Solution

1. Step 1: Single-source vs all-pairs

   Dijkstra/Bellman-Ford compute shortest paths from ONE source to all others. To get all-pairs with Dijkstra, run it V times = O(V(E + V log V)).

2. Step 2: Floyd-Warshall

   Floyd-Warshall computes shortest paths between every pair (i,j) in a single O(V³) pass. Simpler to implement for dense graphs.

3. Final Answer:

   All-pairs shortest paths in one pass. -> Option B

4. Quick Check:

   Floyd-Warshall = all-pairs. Dijkstra = single-source. [OK]

Hint: Floyd-Warshall = all-pairs shortest path. O(V³) time, O(V²) space. [OK]

Common Mistakes:

• Confusing with Dijkstra (single-source)
• Thinking it finds MST
• Confusing with topological sort

2. What is the Floyd-Warshall recurrence? dist[i][j] after considering vertex k as intermediate is:

medium

A. dist[i][j] = dist[i][k] + dist[k][j]

B. dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

C. dist[i][j] = max(dist[i][j], dist[i][k] + dist[k][j])

D. dist[i][j] = dist[i][k] * dist[k][j]

Solution

1. Step 1: Core idea

   For each intermediate vertex k: is the path i→k→j shorter than the current best i→j?

2. Step 2: Recurrence

   dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Keep the minimum of: current best OR going through k.

3. Final Answer:

   min(dist[i][j], dist[i][k] + dist[k][j]) -> Option B

4. Quick Check:

   Always take the minimum - relaxation. [OK]

Hint: Floyd-Warshall: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Relax via each intermediate k. [OK]

Common Mistakes:

• Using + without min (overwrites current best)
• Using max instead of min
• Multiplying instead of adding edge weights

3. In TypeScript, how do you initialize dist[i][i] and dist[i][j] (no direct edge) for Floyd-Warshall?

medium

A. dist[i][i] = 0, dist[i][j] = -1

B. dist[i][i] = 0, dist[i][j] = Infinity

C. dist[i][i] = 1, dist[i][j] = 0

D. dist[i][i] = Infinity, dist[i][j] = Infinity

Solution

1. Step 1: Self-distance

   dist[i][i] = 0 - zero cost to stay at the same vertex.

2. Step 2: No edge

   dist[i][j] = Infinity when no direct edge exists - represents unreachable initially. In TypeScript: Infinity works correctly with Math.min().

3. Final Answer:

   dist[i][i]=0, no edge=Infinity -> Option B

4. Quick Check:

   Self=0, no edge=Infinity. Infinity + x = Infinity in JS - works with min(). [OK]

Hint: Init: self=0, no edge=Infinity. TypeScript Infinity works correctly with Math.min(). [OK]

Common Mistakes:

• Using -1 for no edge (breaks min comparison)
• Setting self-distance to Infinity
• Using 0 for no edge (treats as zero-weight edge)

4. What is the correct loop order for Floyd-Warshall in TypeScript?

hard

A. for i → for j → for k

B. for k → for i → for j

C. for i → for k → for j

D. for j → for k → for i

Solution

1. Step 1: Why k is outermost

   k is the intermediate vertex being 'unlocked' at each outer iteration. When we process intermediate k, all pairs i→j must be relaxed using k.

2. Step 2: Correctness

   If k is innermost, we might use a later-unlocked vertex when relaxing - violating the DP ordering. k must be outermost so all (i,j) pairs are fully relaxed before moving to k+1.

3. Final Answer:

   k outermost, then i, then j. -> Option B

4. Quick Check:

   Floyd-Warshall loop order: k→i→j. k must be outermost. [OK]

Hint: Loop order: k (intermediate) → i (source) → j (dest). k must be outermost - critical for correctness. [OK]

Common Mistakes:

• Putting i outermost (most common mistake)
• Putting j outermost
• Any order other than k→i→j gives wrong results

5. How do you detect a negative cycle using Floyd-Warshall after completion?

hard

A. Check if any dist[i][j] === -Infinity

B. Check if any dist[i][i] < 0 - a vertex with negative self-distance indicates a negative cycle

C. Check if the total sum of all dist values is negative

D. Run the algorithm a second time and compare results

Solution

1. Step 1: Negative cycle effect

   If a negative cycle exists reachable from i back to i, the shortest path dist[i][i] will become negative (going around the cycle reduces cost below 0).

2. Step 2: Detection

   After the algorithm completes, check: for any i, if dist[i][i] < 0, a negative cycle exists involving i.

3. Final Answer:

   Check dist[i][i] < 0 for any i. -> Option B

4. Quick Check:

   Negative cycle: dist[i][i] < 0 after Floyd-Warshall. [OK]

Hint: Negative cycle detection: dist[i][i] < 0 after Floyd-Warshall. Self-distance going negative = cycle. [OK]

Common Mistakes:

• Checking dist[i][j] for non-self pairs
• Summing all distances
• Running algorithm twice