Floyd-Warshall algorithm in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding the core idea of Floyd-Warshall

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

A To detect cycles in a directed graph

B To find the minimum spanning tree of a graph

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

D To perform a depth-first search on a graph

💡 Hint

Think about what kind of paths the algorithm calculates for every pair of points.

The Floyd-Warshall algorithm calculates the shortest distances between every pair of vertices in a weighted graph, even if some edges have negative weights (but no negative cycles).

📋 Factual

intermediate

Time complexity of Floyd-Warshall

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

A O(n^3)

B O(n^2)

C O(n log n)

D O(2^n)

💡 Hint

Consider the three nested loops used in the algorithm.

The Floyd-Warshall algorithm uses three nested loops each running up to n, resulting in O(n^3) time complexity.

🔍 Analysis

advanced

Detecting negative cycles with Floyd-Warshall

After running the Floyd-Warshall algorithm, how can you detect if the graph contains a negative weight cycle?

A Check if any diagonal element in the distance matrix is negative

B Check if any distance value is zero

C Check if the sum of all distances is positive

D Check if any edge weight is negative

💡 Hint

Think about what the diagonal elements represent in the distance matrix.

If any diagonal element (distance from a vertex to itself) becomes negative, it means there is a negative cycle reachable from that vertex.

🚀 Application

advanced

Result of Floyd-Warshall on a specific graph

Given a graph with 3 vertices and edges: 0→1 (weight 4), 1→2 (weight -2), 2→0 (weight 3), what is the shortest distance from vertex 0 to vertex 2 after running Floyd-Warshall?

A 1

B 5

C -2

D 2

💡 Hint

Consider the paths from 0 to 2 and their total weights.

Path 0→1→2 has weight 4 + (-2) = 2, which is shorter than the direct path 0→2 (which does not exist). So the shortest distance is 2.

❓ Reasoning

expert

Why Floyd-Warshall works with negative edges but not negative cycles

Why can the Floyd-Warshall algorithm handle graphs with negative edge weights but fails if there is a negative weight cycle?

A Because negative edges are ignored by the algorithm

B Because negative cycles cause distances to decrease indefinitely, making shortest paths undefined

C Because the algorithm only works on unweighted graphs

D Because negative cycles increase the total path cost

💡 Hint

Think about what happens if you keep going around a negative cycle.

Negative cycles allow infinite reductions in path length by looping, so shortest paths are not well-defined. Floyd-Warshall detects this but cannot produce valid shortest paths in such cases.

Practice

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

easy

A. To perform depth-first search

B. To find the minimum spanning tree

C. To detect cycles in a graph

D. To find shortest paths between all pairs of vertices

Solution

1. Step 1: Understand the algorithm's goal

   The Floyd-Warshall algorithm is designed to find the shortest paths between every pair of vertices in a graph.

2. Step 2: Compare with other graph algorithms

   Minimum spanning tree algorithms find a tree connecting all vertices, cycle detection finds cycles, and DFS explores nodes, none of which match Floyd-Warshall's purpose.

3. Final Answer:

   To find shortest paths between all pairs of vertices -> Option D

4. Quick Check:

   Floyd-Warshall = All pairs shortest paths [OK]

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

Common Mistakes:

• Confusing it with minimum spanning tree algorithms
• Thinking it finds shortest path from one source only
• Mixing it up with cycle detection methods

2. Which of the following correctly represents the core update step in the Floyd-Warshall algorithm for vertices i, j, and k?

easy

A. dist[i][j] = dist[i][k] * dist[k][j]

B. dist[i][j] = max(dist[i][j], dist[i][k] + dist[k][j])

C. dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

D. dist[i][j] = dist[i][j] + dist[k][k]

Solution

1. Step 1: Recall the update formula

   The Floyd-Warshall algorithm updates the shortest distance between i and j by checking if going through k is shorter.

2. Step 2: Identify the correct mathematical operation

   The update uses the minimum of the current distance and the sum of distances through k, which matches dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).

3. Final Answer:

   dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) -> Option C

4. Quick Check:

   Update step uses min sum of paths [OK]

Hint: Update distances using minimum sum through intermediate vertex [OK]

Common Mistakes:

• Using max instead of min
• Multiplying distances instead of adding
• Adding distances incorrectly without min

3. Given the following distance matrix for a graph with vertices 0, 1, 2:

dist = [[0, 3, 999],
        [2, 0, 5],
        [999, 1, 0]]

After running one iteration of Floyd-Warshall with intermediate vertex k=1, what is the updated distance from vertex 0 to vertex 2?

medium

A. 8

B. 5

C. 999

D. 3

Solution

1. Step 1: Identify current distances

   dist[0][2] = 999 (no direct path), dist[0][1] = 3, dist[1][2] = 5.

2. Step 2: Calculate new distance via vertex 1

   New distance = dist[0][1] + dist[1][2] = 3 + 5 = 8, which is less than 999, so update dist[0][2] to 8.

3. Final Answer:

   8 -> Option A

4. Quick Check:

   Updated dist[0][2] = 3 + 5 = 8 [OK]

Hint: Add distances through k and compare with current [OK]

Common Mistakes:

• Not updating because original was 999
• Using dist[0][2] directly without checking intermediate
• Mixing vertex indices

4. Consider this incorrect Floyd-Warshall update step:

for k in range(n):
    for i in range(n):
        for j in range(n):
            if dist[i][j] > dist[i][k] + dist[j][k]:
                dist[i][j] = dist[i][k] + dist[j][k]

What is the main error in this code?

medium

A. The condition uses dist[j][k] instead of dist[k][j]

B. The loops should be reversed in order

C. The update should use max instead of min

D. The code misses initialization of dist matrix

Solution

1. Step 1: Analyze the update condition

   The code compares dist[i][j] with dist[i][k] + dist[j][k], but the second term should be dist[k][j] to represent path i->k->j.

2. Step 2: Identify the correct indexing

   Using dist[j][k] reverses the direction and gives wrong path length, causing incorrect updates.

3. Final Answer:

   The condition uses dist[j][k] instead of dist[k][j] -> Option A

4. Quick Check:

   Correct indexing is dist[k][j] in update [OK]

Hint: Check order of indices in sum: dist[i][k] + dist[k][j] [OK]

Common Mistakes:

• Swapping indices in distance matrix
• Changing loop order unnecessarily
• Confusing min with max in update

5. You have a graph with 4 vertices and the following edges with weights:

(0 -> 1) = 4
(0 -> 2) = 11
(1 -> 2) = -3
(2 -> 3) = 2
(3 -> 1) = 1

Using Floyd-Warshall, what is the shortest distance from vertex 0 to vertex 3 after all iterations?

hard

A. 9

B. 3

C. 6

D. 8

Solution

1. Step 1: Identify possible paths from 0 to 3

   Paths include:
   - 0->1->2->3
   - 0->2->3 directly

2. Step 2: Calculate path distances

   0->1 = 4
   1->2 = -3
   2->3 = 2
   Sum for 0->1->2->3 = 4 + (-3) + 2 = 3
   0->2 = 11
   0->2->3 = 11 + 2 = 13
   Also check 0->1->2->3->1->2->3 cycles but no negative cycle exists.

3. Step 3: Check if going through 3->1->2 improves path

   3->1 = 1, 1->2 = -3, so cycle 1->2->3->1 has total weight 0, no negative cycle.

4. Step 4: Final shortest distance

   Shortest distance from 0 to 3 is 3.

5. Final Answer:

   3 -> Option B

6. Quick Check:

   Shortest distance from 0 to 3 = 4 + (-3) + 2 = 3 [OK]

Hint: Sum edge weights along shortest path carefully [OK]

Common Mistakes:

• Ignoring negative edge weights
• Assuming direct path is shortest
• Not considering cycles properly