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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Floyd Warshall on a 3-node graph

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

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

Use 999 as infinity for no direct edge.
Initial distance matrix:
[[0, 4, 11], [999, 0, 3], [999, 999, 0]]

DSA C++

int dist[3][3] = {
  {0, 4, 11},
  {999, 0, 3},
  {999, 999, 0}
};

for (int k = 0; k < 3; k++) {
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      if (dist[i][k] + dist[k][j] < dist[i][j]) {
        dist[i][j] = dist[i][k] + dist[k][j];
      }
    }
  }
}

// Print dist matrix

A [[0, 4, 7], [999, 0, 3], [999, 999, 0]]

B [[0, 4, 11], [999, 0, 3], [999, 999, 0]]

C [[0, 4, 7], [999, 0, 3], [999, 3, 0]]

D [[0, 7, 10], [999, 0, 3], [999, 999, 0]]

💡 Hint

Check if going through node 1 reduces the distance from 0 to 2.

The shortest path from 0 to 2 is via node 1: 0->1 (4) + 1->2 (3) = 7, which is less than direct 11.

🧠 Conceptual

intermediate

Understanding Floyd Warshall Algorithm

Which statement correctly describes the Floyd Warshall algorithm?

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

B It finds shortest paths from a single source to all other nodes using a priority queue.

C It finds the minimum spanning tree of a graph using edge sorting.

D It finds shortest paths by repeatedly relaxing edges in a queue.

💡 Hint

Think about how the algorithm updates distances using intermediate nodes.

Floyd Warshall updates shortest paths by checking if going through each node k improves the path between i and j.

🔧 Debug

advanced

Identify the error in Floyd Warshall implementation

What error will this Floyd Warshall code cause when run on a graph with no negative cycles?

Code snippet:
for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j]; } } } // dist is a vector> initialized with large values for no edge

DSA C++

for (int k = 0; k < n; k++) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (dist[i][k] + dist[k][j] < dist[i][j])
        dist[i][j] = dist[i][k] + dist[k][j];
    }
  }
}

A Index out of range error accessing dist[i][k]

B Syntax error due to missing braces in if statement

C Integer overflow when adding dist[i][k] + dist[k][j] if one is infinity

D No error, code runs correctly

💡 Hint

Consider what happens when dist[i][k] or dist[k][j] is set to a large value representing infinity.

Adding large infinity values can overflow int and produce incorrect results, so checks are needed before addition.

📝 Syntax

advanced

Correct syntax for Floyd Warshall update condition

Which option is the correct syntax for updating the distance matrix in Floyd Warshall in C++?

A if dist[i][k] + dist[k][j] < dist[i][j] then dist[i][j] = dist[i][k] + dist[k][j];

B if (dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j];

C if (dist[i][k] + dist[k][j] < dist[i][j]) { dist[i][j] == dist[i][k] + dist[k][j]; }

D if (dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] := dist[i][k] + dist[k][j];

💡 Hint

Remember C++ uses parentheses for conditions and single equals for assignment.

Option B uses correct C++ syntax: if(condition) statement; with assignment using =.

🚀 Application

expert

Detecting negative cycles using Floyd Warshall

After running Floyd Warshall on a graph, how can you detect if the graph contains a negative weight cycle?

A Check if the graph has more edges than nodes

B Check if any dist[i][j] is still infinity after the algorithm

C Check if the sum of all dist[i][j] is negative

D Check if any dist[i][i] < 0 for any node i

💡 Hint

Think about what a negative cycle means for the distance from a node to itself.

A negative cycle causes the distance from a node to itself to become negative after Floyd Warshall.

Practice

1. What is the main purpose of the Floyd Warshall algorithm in graph theory?

easy

A. To find shortest paths between all pairs of vertices in a weighted graph

B. To find the minimum spanning tree of a graph

C. To detect cycles in a directed graph

D. To perform depth-first search traversal

Solution

1. Step 1: Understand Floyd Warshall algorithm goal

   The Floyd Warshall algorithm is designed to find shortest paths between every pair of vertices in a weighted graph, including negative weights but no negative cycles.

2. Step 2: Compare with other graph algorithms

   Minimum spanning tree algorithms find a tree connecting all vertices with minimum total edge weight, cycle detection algorithms find cycles, and DFS is a traversal method. These are different from Floyd Warshall's goal.

3. Final Answer:

   To find shortest paths between all pairs of vertices in a weighted graph -> Option A

4. Quick Check:

   Floyd Warshall = all pairs shortest paths [OK]

Hint: Floyd Warshall finds shortest paths between all vertex pairs [OK]

Common Mistakes:

• Confusing Floyd Warshall with minimum spanning tree algorithms
• Thinking it only finds shortest path from one source
• Assuming it detects cycles instead of paths

2. Which of the following is the correct way to initialize the distance matrix dist for Floyd Warshall in C++ for a graph with n vertices and adjacency matrix graph?

easy

A. for (int i = 0; i < n; i++) dist[i] = graph[i];

B. for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dist[i][j] = graph[i][j];

C. dist = graph;

D. dist = new int[n][n];

Solution

1. Step 1: Understand distance matrix initialization

   We need to copy each element from the adjacency matrix graph to dist element-wise because dist is a 2D array and direct assignment is not allowed in C++.

2. Step 2: Analyze each option

   for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dist[i][j] = graph[i][j]; uses nested loops to copy each element correctly. for (int i = 0; i < n; i++) dist[i] = graph[i]; tries to assign a row pointer which is invalid for 2D arrays. dist = graph; tries direct assignment which is invalid for arrays. dist = new int[n][n]; only allocates memory but does not initialize values.

3. Final Answer:

   for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dist[i][j] = graph[i][j]; -> Option B

4. Quick Check:

   Element-wise copy needed = for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dist[i][j] = graph[i][j]; [OK]

Hint: Use nested loops to copy 2D arrays element-wise [OK]

Common Mistakes:

• Trying to assign 2D arrays directly
• Copying only row pointers instead of elements
• Not initializing distance matrix before algorithm

3. What will be the output distance matrix after running Floyd Warshall on the following graph with 3 vertices and adjacency matrix:

int graph[3][3] = {
  {0, 5, 999},
  {50, 0, 15},
  {30, 999, 0}
};

Assuming 999 represents no direct edge.

medium

A. [[0, 5, 20], [50, 0, 15], [30, 35, 0]]

B. [[0, 5, 999], [50, 0, 15], [30, 999, 0]]

C. [[0, 5, 999], [50, 0, 15], [30, 45, 0]]

D. [[0, 5, 20], [45, 0, 15], [30, 35, 0]]

Solution

1. Step 1: Initialize distance matrix

   Start with dist = graph:
   dist = [[0,5,999],[50,0,15],[30,999,0]]

2. Step 2: Update distances using Floyd Warshall

   Check if going through vertex 0 improves paths:
   dist[1][2] = min(15, dist[1][0]+dist[0][2]) = min(15, 50+999)=15 (no change)
   dist[2][1] = min(999, dist[2][0]+dist[0][1]) = min(999, 30+5)=35 (updated)
   Check through vertex 1:
   dist[0][2] = min(999, dist[0][1]+dist[1][2]) = min(999, 5+15)=20 (updated)
   dist[2][2] = min(0, dist[2][1]+dist[1][2]) = min(0, 35+15)=0 (no change)
   Check through vertex 2:
   dist[1][0] = min(50, dist[1][2]+dist[2][0]) = min(50, 15+30)=45 (updated)

3. Final Answer:

   [[0, 5, 20], [45, 0, 15], [30, 35, 0]] -> Option D

4. Quick Check:

   Updated shortest paths matrix = [[0, 5, 20], [45, 0, 15], [30, 35, 0]] [OK]

Hint: Check all intermediate vertices to update shortest paths [OK]

Common Mistakes:

• Not updating paths through intermediate vertices
• Confusing no edge (999) with zero
• Missing updates for reverse paths

4. Identify the error in this Floyd Warshall code snippet and select the fix:

for (int k = 0; k < n; k++) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (dist[i][k] + dist[k][j] < dist[i][j])
        dist[i][j] = dist[i][k] + dist[k][j];
    }
  }
}

medium

A. Check if dist[i][k] and dist[k][j] are not infinity before adding

B. No error; code is correct

C. Change loop order to i, j, k

D. Use max instead of min in the if condition

Solution

1. Step 1: Understand potential overflow in addition

   If dist[i][k] or dist[k][j] is infinity (representing no path), adding them causes incorrect results or overflow.

2. Step 2: Fix by checking for infinity before addition

   Before adding dist[i][k] + dist[k][j], ensure both are not infinity to avoid invalid updates.

3. Final Answer:

   Check if dist[i][k] and dist[k][j] are not infinity before adding -> Option A

4. Quick Check:

   Prevent invalid addition by checking infinity [OK]

Hint: Always check for infinity before adding distances [OK]

Common Mistakes:

• Ignoring infinity checks causing wrong updates
• Changing loop order incorrectly
• Using max instead of min for shortest path

5. Given a weighted directed graph with 4 vertices and adjacency matrix:

int graph[4][4] = {
  {0, 3, 999, 7},
  {8, 0, 2, 999},
  {5, 999, 0, 1},
  {2, 999, 999, 0}
};

Use Floyd Warshall to find the shortest path distance from vertex 0 to vertex 3 after all updates. What is the shortest distance?

hard

A. 8

B. 7

C. 6

D. 9

Solution

1. Step 1: Initialize distance matrix

   Start with dist = graph:
   dist = [[0,3,999,7],[8,0,2,999],[5,999,0,1],[2,999,999,0]]

2. Step 2: Update distances through intermediate vertices

   Check paths through vertex 0:
   dist[1][3] = min(999, dist[1][0]+dist[0][3]) = min(999, 8+7)=15
   dist[2][1] = min(999, dist[2][0]+dist[0][1]) = min(999, 5+3)=8
   dist[3][1] = min(999, dist[3][0]+dist[0][1]) = min(999, 2+3)=5
   Check paths through vertex 1:
   dist[0][2] = min(999, dist[0][1]+dist[1][2]) = min(999, 3+2)=5
   dist[0][3] = min(7, dist[0][1]+dist[1][3]) = min(7, 3+15)=7
   dist[3][2] = min(999, dist[3][1]+dist[1][2]) = min(999, 5+2)=7
   Check paths through vertex 2:
   dist[1][3] = min(15, dist[1][2]+dist[2][3]) = min(15, 2+1)=3 (updated)
   dist[0][3] = min(7, dist[0][2]+dist[2][3]) = min(7, 5+1)=6 (updated)
   Check paths through vertex 3:
   dist[2][0] = min(5, dist[2][3]+dist[3][0]) = min(5, 1+2)=3 (updated)

3. Final Answer:

   6 -> Option C

4. Quick Check:

   Shortest path 0 to 3 = 6 [OK]

Hint: Update distances through all vertices stepwise [OK]

Common Mistakes:

• Not updating paths through all intermediate vertices
• Missing shorter path updates
• Confusing direct edge with shortest path