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.