Floyd Warshall All Pairs Shortest Path in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Floyd Warshall on a simple graph

What is the output distance matrix after running Floyd Warshall on this graph?

Graph edges with weights:
0 -> 1 (3), 0 -> 2 (8), 1 -> 2 (2), 2 -> 3 (1), 3 -> 0 (4)

Use Infinity for no direct path.
Initial matrix (4x4):
[[0, 3, 8, Infinity],
[Infinity, 0, 2, Infinity],
[Infinity, Infinity, 0, 1],
[4, Infinity, Infinity, 0]]

DSA Typescript

const INF = Infinity;
const dist = [
  [0, 3, 8, INF],
  [INF, 0, 2, INF],
  [INF, INF, 0, 1],
  [4, INF, INF, 0]
];
const V = 4;
for (let k = 0; k < V; k++) {
  for (let i = 0; i < V; i++) {
    for (let j = 0; j < V; j++) {
      if (dist[i][k] + dist[k][j] < dist[i][j]) {
        dist[i][j] = dist[i][k] + dist[k][j];
      }
    }
  }
}
console.log(dist);

A [[0, 3, 5, 7],[8, 0, 2, 3],[5, 8, 0, 1],[4, 7, 9, 0]]

B [[0, 3, 8, 9],[Infinity, 0, 2, 3],[Infinity, Infinity, 0, 1],[4, 7, 12, 0]]

C [[0, 3, 5, 6],[7, 0, 2, 3],[5, 8, 0, 1],[4, 7, 9, 0]]

D ]]0 ,21 ,7 ,4[,]1 ,0 ,ytinifnI ,ytinifnI[,]3 ,2 ,0 ,ytinifnI[,]9 ,8 ,3 ,0[[

💡 Hint

Trace the shortest paths through intermediate vertices step by step.

Option C shows the correct shortest distances after considering all intermediate vertices. For example, distance from 0 to 2 is updated from 8 to 5 via vertex 1 (0->1->2).

🧠 Conceptual

intermediate

Understanding Floyd Warshall's time complexity

What is the time complexity of the Floyd Warshall algorithm for a graph with V vertices?

A O(V^2)

B O(V log V)

C O(V^4)

D O(V^3)

💡 Hint

Consider the three nested loops over vertices.

Floyd Warshall uses three nested loops each running V times, resulting in O(V^3) time complexity.

🔧 Debug

advanced

Identify the error in Floyd Warshall implementation

What error will this code produce when running Floyd Warshall?

Code snippet:
for (let k = 0; k < V; k++) { for (let i = 0; i < V; i++) { for (let j = 0; j < V; j++) { if (dist[i][k] + dist[k][j] < dist[i][j]) { dist[i][j] = dist[i][k] + dist[k][j]; } } } }

DSA Typescript

const V = 3;
const dist = [
  [0, 5, Infinity],
  [50, 0, 15],
  [30, Infinity, 0]
];
for (let k = 0; k < V; k++) {
  for (let i = 0; i < V; i++) {
    for (let j = 0; j < V; j++) {
      if (dist[i][k] + dist[k][j] < dist[i][j]) {
        dist[i][j] = dist[i][k] + dist[k][j];
      }
    }
  }
}
console.log(dist);

A No error, outputs correct shortest paths

B TypeError: Cannot add Infinity to a number

C NaN values appear in the matrix

D Runtime error due to index out of bounds

💡 Hint

Infinity plus a number is still Infinity in JavaScript.

Adding Infinity to a number in JavaScript results in Infinity, so no error occurs. The code correctly updates shortest paths.

🚀 Application

advanced

Detecting negative cycles with Floyd Warshall

How can Floyd Warshall algorithm detect a negative weight cycle in a graph?

A If any element dist[i][j] is Infinity after the algorithm finishes

B If any diagonal element dist[i][i] becomes negative after the algorithm finishes

C If the sum of all distances in dist matrix is negative

D If the number of edges is greater than vertices

💡 Hint

Think about shortest path from a vertex to itself.

A negative value on the diagonal dist[i][i] means a negative cycle reachable from vertex i.

❓ Predict Output

expert

Output of Floyd Warshall on a graph with unreachable nodes

Given this initial distance matrix for a graph with 3 vertices:
[[0, 7, Infinity], [Infinity, 0, Infinity], [2, Infinity, 0]]
What is the final distance matrix after running Floyd Warshall?

DSA Typescript

const INF = Infinity;
const dist = [
  [0, 7, INF],
  [INF, 0, INF],
  [2, INF, 0]
];
const V = 3;
for (let k = 0; k < V; k++) {
  for (let i = 0; i < V; i++) {
    for (let j = 0; j < V; j++) {
      if (dist[i][k] + dist[k][j] < dist[i][j]) {
        dist[i][j] = dist[i][k] + dist[k][j];
      }
    }
  }
}
console.log(dist);

A [[0, 7, Infinity],[Infinity, 0, Infinity],[2, 9, 0]]

B [[0, 7, Infinity],[Infinity, 0, Infinity],[2, Infinity, 0]]

C [[0, 7, Infinity],[Infinity, 0, Infinity],[Infinity, Infinity, 0]]

D [[0, 7, Infinity],[Infinity, 0, Infinity],[2, 7, 0]]

💡 Hint

Check if vertex 2 can reach vertex 1 through vertex 0.

Vertex 2 can reach vertex 1 via vertex 0 with distance 2 + 7 = 9, updating dist[2][1]. Other unreachable paths remain Infinity.

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