Floyd Warshall All Pairs Shortest Path in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main purpose of the Floyd Warshall algorithm?

It finds the shortest paths between all pairs of vertices in a weighted graph, including graphs with negative edge weights but no negative cycles.

beginner

In Floyd Warshall, what does the matrix entry dist[i][j] represent during the algorithm?

It represents the shortest known distance from vertex i to vertex j considering intermediate vertices processed so far.

intermediate

Why does Floyd Warshall use three nested loops?

Because it iterates over all pairs of vertices (i, j) and tries to improve the path by checking an intermediate vertex k, updating dist[i][j] if a shorter path is found.

intermediate

What is the time complexity of the Floyd Warshall algorithm?

O(V³), where V is the number of vertices in the graph, due to the three nested loops over all vertices.

intermediate

How does Floyd Warshall handle graphs with negative edge weights?

It correctly computes shortest paths even with negative edges, as long as there are no negative weight cycles reachable from any vertex.

What does Floyd Warshall algorithm compute?

A Shortest paths between all pairs of vertices

B Shortest path from a single source to all vertices

C Minimum spanning tree

D Topological sort

Floyd Warshall finds shortest paths between every pair of vertices.

Which of these is a requirement for Floyd Warshall to work correctly?

A No negative weight cycles

B Graph must be acyclic

C Graph must be undirected

D All edges must have positive weights

Floyd Warshall works with negative edges but not with negative weight cycles.

What is the initial value of dist[i][j] if there is no direct edge between i and j?

A 0

B Infinity (a very large number)

C -1

D 1

Distances are set to infinity if no direct edge exists initially.

How many nested loops does Floyd Warshall use?

A 1

B 2

C 3

D 4

Three nested loops iterate over k, i, and j vertices.

What does the variable 'k' represent in Floyd Warshall?

A Current source vertex

B Current destination vertex

C Number of edges

D Intermediate vertex being considered

'k' is the intermediate vertex used to check if paths can be improved.

Explain how Floyd Warshall algorithm updates the shortest path matrix step-by-step.

Think about checking if going through an intermediate vertex shortens the path.

Describe the conditions under which Floyd Warshall algorithm can handle negative edge weights and when it fails.

Consider what happens if you can keep reducing path length indefinitely.

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