Floyd Warshall All Pairs Shortest Path in DSA C# - 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 9999 to represent infinity.

Initial distance matrix (4 vertices):
[[0, 3, 8, 9999], [9999, 0, 2, 9999], [9999, 9999, 0, 1], [4, 9999, 9999, 0]]

DSA C#

int INF = 9999;
int[,] dist = {
  {0, 3, 8, INF},
  {INF, 0, 2, INF},
  {INF, INF, 0, 1},
  {4, INF, INF, 0}
};
int V = 4;
for (int k = 0; k < V; k++) {
  for (int i = 0; i < V; i++) {
    for (int j = 0; j < V; j++) {
      if (dist[i,j] > dist[i,k] + dist[k,j]) {
        dist[i,j] = dist[i,k] + dist[k,j];
      }
    }
  }
}
// Print dist matrix

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

B [[0, 3, 5, 6], [9999, 0, 2, 3], [9999, 9999, 0, 1], [4, 7, 9, 0]]

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

D [[0, 3, 8, 9], [9999, 0, 2, 3], [9999, 9999, 0, 1], [4, 7, 15, 0]]

💡 Hint

Trace the shortest paths step by step using intermediate vertices.

Floyd Warshall updates distances by checking if going through an intermediate vertex k gives a shorter path. After all iterations, the matrix shows shortest distances between all pairs.

🧠 Conceptual

intermediate

Understanding Floyd Warshall Algorithm Complexity

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

A O(V^3)

B O(V^2)

C O(V * E)

D O(E^2)

💡 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 bug in Floyd Warshall implementation

What error will this code cause when running Floyd Warshall?

Code snippet:
int INF = 9999;
int[,] dist = new int[V,V];
// dist initialized with INF except dist[i,i] = 0
for (int k = 0; k < V; k++) { for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { if (dist[i,j] > dist[i,k] + dist[k,j]) { dist[i,j] = dist[i,k] + dist[k,j]; } } } }

A No error, runs correctly

B Possible integer overflow when adding dist[i,k] + dist[k,j]

C NullReferenceException because dist is not initialized

D IndexOutOfRangeException due to wrong array size

💡 Hint

Check what happens when dist[i,k] or dist[k,j] is INF.

Adding INF (9999) to another number can exceed int max or produce incorrect results, causing overflow or wrong comparisons.

📝 Syntax

advanced

Syntax error in Floyd Warshall nested loops

Which option contains a syntax error in the Floyd Warshall nested loops?

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

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

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

C } } } } ;]j,k[tsid + ]k,i[tsid = ]j,i[tsid { )]j,k[tsid + ]k,i[tsid > ]j,i[tsid( fi { )++j ;V < j ;0 = j tni( rof { )++i ;V < i ;0 = i tni( rof { )++k ;V < k ;0 = k tni( rof

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

💡 Hint

Check the syntax of the for loop declarations.

In C#, for loops require parentheses around initialization, condition, and increment. Option D misses parentheses causing syntax error.

🚀 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 If the sum of all dist[i,j] is negative, the graph has a negative cycle

B If any dist[i,j] is infinity, the graph has a negative cycle

C If any dist[i,i] < 0 for any vertex i, the graph has a negative cycle

D If any dist[i,j] > dist[j,i], the graph has a negative cycle

💡 Hint

Check the diagonal elements of the distance matrix after the algorithm.

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

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