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 input graph.

DSA C#

int V = graph.GetLength(0);
int[,] dist = new int[V, V];
for (int i = 0; i < V; i++)
{
    for (int j = 0; j < V; j++)
    {
        dist[i, j] = graph[i, j] == 0 && i != j ? [1] : graph[i, j];
    }
}

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

Aint.MaxValue

B1

C0

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of a large number causes incorrect shortest path calculations.

Using -1 can cause confusion with valid edge weights.

We use int.MaxValue to represent no direct edge between nodes (infinity).

2fill in blank

medium

Complete the code to update the distance matrix using the Floyd Warshall algorithm.

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] != int.MaxValue && dist[k, j] != int.MaxValue && dist[i, k] + dist[k, j] < [1])
            {
                dist[i, j] = dist[i, k] + dist[k, j];
            }
        }
    }
}

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

Adist[i, j]

Bdist[k, j]

Cint.MaxValue

Ddist[i, k]

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with dist[i, k] or dist[k, j] instead of dist[i, j].

Using int.MaxValue in comparison causes wrong logic.

We update dist[i, j] only if the new path through k is shorter than the current dist[i, j].

3fill in blank

hard

Fix the error in the code that prints the final shortest path matrix.

DSA C#

for (int i = 0; i < V; i++)
{
    for (int j = 0; j < V; j++)
    {
        if (dist[i, j] == [1])
            Console.Write("INF ");
        else
            Console.Write(dist[i, j] + " ");
    }
    Console.WriteLine();
}

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

Anull

B0

C-1

Dint.MaxValue

Attempts:

3 left

💡 Hint

Common Mistakes

Checking for 0 instead of int.MaxValue causes wrong output.

Using null causes compilation errors in C#.

Distances with int.MaxValue mean no path, so print 'INF' for clarity.

4fill in blank

hard

Fill both blanks to complete the nested loops for Floyd Warshall algorithm.

DSA C#

for (int [1] = 0; [1] < V; [1]++)
{
    for (int [2] = 0; [2] < V; [2]++)
    {
        // inner logic
    }
}

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

Ai

Bk

Cj

Dx

Attempts:

3 left

💡 Hint

Common Mistakes

Using same variable name for both loops causes errors.

Using j in outer loop breaks the algorithm logic.

The outer loop uses k as intermediate node, inner uses i for source nodes.

5fill in blank

hard

Fill all three blanks to complete the triple nested loops for Floyd Warshall algorithm.

DSA C#

for (int [1] = 0; [1] < V; [1]++)
{
    for (int [2] = 0; [2] < V; [2]++)
    {
        for (int [3] = 0; [3] < V; [3]++)
        {
            // update dist logic
        }
    }
}

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

Ak

Bi

Cj

Dm

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing loop variable names breaks the algorithm.

Using same variable for multiple loops causes errors.

The loops iterate over k (intermediate), i (source), and j (destination) nodes respectively.

Practice

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

easy

A. To perform a depth-first search traversal

B. To find the minimum spanning tree of a graph

C. To detect cycles in a graph

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

Solution

1. Step 1: Understand Floyd Warshall's goal

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

2. Step 2: Compare with other algorithms

   Minimum spanning tree algorithms find a tree connecting all vertices with minimum total weight, cycle detection finds loops, and DFS is a traversal method, none of which match Floyd Warshall's purpose.

3. Final Answer:

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

4. Quick Check:

   Floyd Warshall = All pairs shortest paths [OK]

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

Common Mistakes:

• Confusing with minimum spanning tree algorithms
• Thinking it only finds shortest path from one source
• Assuming it works with negative cycles

2. Which of the following is the correct way to initialize the distance matrix dist for Floyd Warshall in C# when given an adjacency matrix graph of size V?

easy

A. for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { dist[i, j] = graph[i, j]; } }

B. for (int i = 0; i < V; i++) { dist[i, i] = 0; } for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { if (i != j) dist[i, j] = int.MaxValue; } }

C. for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { dist[i, j] = 0; } }

D. for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { dist[i, j] = -1; } }"

Solution

1. Step 1: Understand initialization for Floyd Warshall

   The distance matrix dist should start as a copy of the adjacency matrix graph because it holds initial edge weights or infinity where no edge exists.

2. Step 2: Check each option

   for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { dist[i, j] = graph[i, j]; } } copies graph to dist, which is correct. for (int i = 0; i < V; i++) { dist[i, i] = 0; } for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { if (i != j) dist[i, j] = int.MaxValue; } } sets 0 for diagonal and max value elsewhere but does not copy actual edges. Options C and D incorrectly set all distances to 0 or -1.

3. Final Answer:

   for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { dist[i, j] = graph[i, j]; } } -> Option A

4. Quick Check:

   Initialize dist as graph copy [OK]

Hint: Copy graph matrix to dist for Floyd Warshall start [OK]

Common Mistakes:

• Setting all distances to zero
• Not copying actual edge weights
• Using -1 instead of infinity for no edge

3. Consider the following C# code snippet implementing Floyd Warshall on a graph with 3 vertices and adjacency matrix:

int V = 3;
int[,] graph = {
  {0, 5, int.MaxValue},
  {50, 0, 15},
  {30, int.MaxValue, 0}
};

int[,] dist = new int[V, V];
for (int i = 0; i < V; i++)
  for (int j = 0; j < V; j++)
    dist[i, j] = graph[i, j];

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] != int.MaxValue && dist[k, j] != int.MaxValue && dist[i, k] + dist[k, j] < dist[i, j]) {
        dist[i, j] = dist[i, k] + dist[k, j];
      }
    }
  }
}

// Print dist matrix
for (int i = 0; i < V; i++) {
  for (int j = 0; j < V; j++) {
    Console.Write(dist[i, j] == int.MaxValue ? "INF " : dist[i, j] + " ");
  }
  Console.WriteLine();
}

What is the printed output?

medium

A. 0 5 20
50 0 15
30 INF 0

B. 0 5 20
45 0 15
30 35 0

C. 0 5 INF
50 0 15
30 INF 0

D. 0 5 15
50 0 15
30 35 0

Solution

1. Step 1: Initialize dist matrix

   dist starts as: 0 5 INF 50 0 15 30 INF 0

2. Step 2: Apply Floyd Warshall updates

   Check paths through each vertex k: - k=0: Update dist[1,2] via 1->0->2: 50 + INF no update; dist[2,1] via 2->0->1: 30 + 5 = 35 < INF, update dist[2,1] = 35 - k=1: Update dist[0,2] via 0->1->2: 5 + 15 = 20 < INF, update dist[0,2] = 20 - k=2: No further improvements Final dist: 0 5 20 45 0 15 30 35 0

3. Final Answer:

   0 5 20 45 0 15 30 35 0 -> Option B

4. Quick Check:

   Floyd Warshall updates shortest paths correctly [OK]

Hint: Check all intermediate vertices k for shorter paths [OK]

Common Mistakes:

• Not updating dist when shorter path found
• Confusing INF with int.MaxValue in output
• Missing updates for indirect paths

4. The following C# code attempts to implement Floyd Warshall but produces incorrect results. What is the main bug?

int V = 3;
int[,] dist = new int[V, V];
for (int i = 0; i < V; i++)
  for (int j = 0; j < V; j++)
    dist[i, j] = graph[i, j];

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

Choose the correct bug:

medium

A. The condition does not check for int.MaxValue before addition

B. The initialization of dist is missing

C. The order of loops is incorrect; k should be the outer loop

D. The code uses wrong indices in the if condition

Solution

1. Step 1: Analyze loop order

   Floyd Warshall requires the outer loop to be over intermediate vertex k, then loops over i and j to update paths through k.

2. Step 2: Identify impact of loop order

   Current code loops i, j, then k, which does not correctly consider all intermediate vertices before updating distances, leading to incorrect results.

3. Final Answer:

   The order of loops is incorrect; k should be the outer loop -> Option C

4. Quick Check:

   Loop order: k outermost for Floyd Warshall [OK]

Hint: Outer loop must be intermediate vertex k [OK]

Common Mistakes:

• Not checking for int.MaxValue before addition
• Incorrect loop nesting order
• Forgetting to initialize dist properly

5. You have a weighted directed graph with 4 vertices and the following adjacency matrix (where INF means no direct edge):

int INF = int.MaxValue;
int[,] graph = {
  {0, 3, INF, 7},
  {8, 0, 2, INF},
  {5, INF, 0, 1},
  {2, INF, INF, 0}
};

Using Floyd Warshall, what is the shortest distance from vertex 3 to vertex 1 after the algorithm completes?

hard

A. 5

B. 7

C. 6

D. 3

Solution

1. Step 1: Understand the graph and indexing

   Vertices are 0-based: vertex 3 means index 3, vertex 1 means index 1. Initial dist[3,1] = INF (no direct edge).

2. Step 2: Apply Floyd Warshall updates to find shortest path from 3 to 1

   Check possible paths: - Direct: INF - Via 0: dist[3,0] + dist[0,1] = 2 + 3 = 5 - Via 2: dist[3,2] + dist[2,1] = INF + INF = INF - Other paths do not improve Therefore shortest distance is 5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Shortest path 3->0->1 = 2+3=5 [OK]

Hint: Trace paths through intermediate vertices to find shortest distance [OK]

Common Mistakes:

• Confusing vertex numbering (0-based vs 1-based)
• Ignoring indirect paths through intermediate vertices
• Assuming direct edge must exist