1.8. Space Complexity Considerations

Try these first

1. 1.

   What does the Floyd-Warshall algorithm compute?

   Hint

   Think about what you want to find in the graph.

2. 2.

   Does the Floyd-Warshall algorithm work with negative edge weights?

   Hint

   Consider what negative cycles do to path calculations.

3. 3.

   What is the time complexity of the Floyd-Warshall algorithm?

   • O(n)
   • O(n²)
   • O(n³)

   Hint

   Think about how many vertices are involved in the updates.

4. 4.

   True or False: The Floyd-Warshall algorithm can handle graphs with negative cycles.

   • True
   • False

   Hint

   Remember that negative cycles alter path finding.

5. 5.

   Consider a directed graph with vertices A, B, C, and D. The edges are as follows: A to B (3), A to C (5), B to D (2), and C to D (1). Compute the shortest paths between all pairs using the Floyd-Warshall method.

   Hint

   Use the initial weight matrix to track distances through each step.

6. 6.

   Design an example graph that contains a negative cycle. Explain why the Floyd-Warshall algorithm cannot provide a valid solution for this graph.

   Hint

   Focus on how negative edge weights contribute to cycles when combined.