Floyd Warshall All Pairs Shortest Path in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the distance matrix with the given graph edges.

DSA C++

for (int i = 0; i < V; i++) {
    for (int j = 0; j < V; j++) {
        if (i == j) dist[i][j] = 0;
        else dist[i][j] = [1];
    }
}

Drag options to blanks, or click blank then click option'

A0

B-1

CINT_MAX

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 for no edge causes incorrect shortest path calculations.

Using negative values can cause wrong results.

We use INT_MAX to represent no direct edge between nodes, meaning infinite distance initially.

2fill in blank

medium

Complete the code to update the distance matrix with the direct edges from the graph.

DSA C++

for (auto edge : edges) {
    int u = edge.first;
    int v = edge.second.first;
    int w = edge.second.second;
    dist[u][v] = [1];
}

Drag options to blanks, or click blank then click option'

Aw

Bu

Cv

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning node indices instead of weight.

Assigning zero which ignores edge weight.

We assign the weight w of the edge from u to v to the distance matrix.

3fill in blank

hard

Fix the error in the Floyd Warshall triple nested loop condition to avoid integer overflow.

DSA C++

for (int k = 0; k < V; k++) {
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (dist[i][k] != [1] && dist[k][j] != [1] && dist[i][k] + dist[k][j] < dist[i][j]) {
                dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
}

Drag options to blanks, or click blank then click option'

AINT_MAX

B0

C1

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Not checking for INT_MAX causes overflow and wrong results.

Checking for zero or negative values is incorrect here.

We check that dist[i][k] and dist[k][j] are not INT_MAX to avoid overflow when adding.

4fill in blank

hard

Fill both blanks to print the shortest distance matrix after Floyd Warshall completes.

DSA C++

for (int i = 0; i < V; i++) {
    for (int j = 0; j < V; j++) {
        if (dist[i][j] == [1]) std::cout << "INF" << [2];
        else std::cout << dist[i][j] << " ";
    }
    std::cout << std::endl;
}

Drag options to blanks, or click blank then click option'

AINT_MAX

B" "

C"\t"

D"\n"

Attempts:

3 left

💡 Hint

Common Mistakes

Printing INT_MAX as a number confuses output.

Using space instead of tab may reduce readability.

We print "INF" for infinite distances and separate values with a tab for readability.

5fill in blank

hard

Fill all three blanks to complete the Floyd Warshall update step with correct indices and condition.

DSA C++

for (int k = 0; k < V; k++) {
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (dist[i][k] != [1] && dist[k][j] != [1] && dist[i][k] + dist[k][j] < dist[[2]][[3]]) {
                dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
}

Drag options to blanks, or click blank then click option'

AINT_MAX

Bi

Cj

Dk

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong indices in dist update condition.

Not checking for INT_MAX before addition.

We check for INT_MAX to avoid overflow and update dist[i][j] if a shorter path is found.

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