1.10. Warshall's Algorithm and Transitive Closure

Try these first

1. 1.

   What is Warshall's Algorithm used for?

   Hint

   Think about connectivity between vertices.

2. 2.

   What is the typical initial state of an adjacency matrix?

   Hint

   Consider how edges are represented.

3. 3.

   What does Warshall's Algorithm compute?

   • Shortest paths
   • Transitive Closure
   • Graph coloring

   Hint

   Think about how reachability is defined.

4. 4.

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

   • True
   • False

   Hint

   Consider the implications of a negative cycle.

5. 5.

   Given a directed graph with weights, apply the Floyd-Warshall algorithm to find all pairs shortest paths. Write down each step leading to the final matrix.

   Hint

   Keep track of how weights update as you consider intermediate vertices.

6. 6.

   Construct an example with a negative cycle and demonstrate what happens when using Floyd-Warshall.

   Hint

   Think about what happens if a path gets shorter with each iteration through the cycle.