1.7. Complexity Analysis of Floyd-Warshall Algorithm

Try these first

1. 1.

   What does the Floyd-Warshall algorithm compute?

   Hint

   Think about what problems you can solve with pathfinding.

2. 2.

   Can the Floyd-Warshall algorithm handle negative weights?

   Hint

   Consider the implications of negative cycles on pathfinding.

3. 3.

   What is the primary purpose of the Floyd-Warshall algorithm?

   • Find minimum spanning tree
   • Compute shortest paths between all pairs
   • Sort the vertices

   Hint

   Recall what this algorithm is designed for in the context of graphs.

4. 4.

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

   • True
   • False

   Hint

   Think about the rules concerning weights in graphs.

5. 5.

   Create a weighted graph with at least 5 vertices containing both negative and positive weights. Apply the Floyd-Warshall algorithm to find the shortest paths and discuss the results.

   Hint

   Make sure to include the edges and their weights clearly.

6. 6.

   Analyze a scenario where the Floyd-Warshall fails due to a negative cycle present in the graph. Explain the consequences.

   Hint

   Reflect on what a negative cycle does to pathweight over cycles.