1.4. Introduction of the Floyd-Warshall Algorithm

Try these first

1. 1.

   What does the Floyd-Warshall algorithm solve?

   Hint

   Think about the connections between all vertices.

2. 2.

   Can the Floyd-Warshall algorithm work with negative weights?

   Hint

   Consider how negative weights affect paths.

3. 3.

   What does the Floyd-Warshall algorithm accomplish?

   • Finds single source paths
   • Finds shortest paths between all vertex pairs
   • Identifies negative cycles

   Hint

   Reflect on what 'all-pairs' means.

4. 4.

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

   • True
   • False

   Hint

   Remember what defines a cycle in this context.

5. 5.

   Consider a graph with negative edges but no cycles. Apply the Floyd-Warshall algorithm and outline your distance matrix updates.

   Hint

   Start with a diagram.

6. 6.

   Analyze the efficiency trade-offs between Floyd-Warshall and Dijkstra's algorithm for various types of graphs.

   Hint

   Compare the number of edges vs vertices.