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.