Floyd Warshall All Pairs Shortest Path in DSA C# - Time & Space Complexity

Time Complexity: Floyd Warshall All Pairs Shortest Path

O(n³)

Understanding Time Complexity

We want to understand how the time needed to find shortest paths between all pairs of points grows as the number of points increases.

How does the running time change when we add more points to the map?

Scenario Under Consideration

Analyze the time complexity of the following 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];
        }
    }
}
    

This code updates the shortest distances between all pairs of points by checking if going through an intermediate point k gives a shorter path.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The triple nested loops that update distances.
• How many times: Each loop runs n times, so the inner update runs n x n x n = n³ times.

How Execution Grows With Input

As the number of points n grows, the number of operations grows very fast because we check every pair with every possible intermediate point.

Input Size (n)	Approx. Operations
10	1,000
100	1,000,000
1000	1,000,000,000

Pattern observation: When n increases 10 times, operations increase 1000 times (cube growth).

Final Time Complexity

Time Complexity: O(n³)

This means the time needed grows roughly with the cube of the number of points, so doubling points makes it take about eight times longer.

Common Mistake

[X] Wrong: "Since there are three loops, the time complexity is just O(n)."

[OK] Correct: Each loop runs n times independently, so the total work multiplies, making it n x n x n = n³, not just n.

Interview Connect

Understanding this cubic time complexity helps you explain why Floyd Warshall is good for small graphs but not for very large ones, showing you know when to choose algorithms wisely.

Self-Check

"What if we replaced the triple nested loops with a recursive approach? How would the time complexity change?"

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