1.1. Introduction to All-pairs Shortest Paths

Try these first

1. 1.

   What is the All-pairs Shortest Paths problem?

   Hint

   Think about a scenario involving multiple locations.

2. 2.

   Can a graph have negative cycles?

   Hint

   Consider the implications of having a cycle with negative weights.

3. 3.

   What does the Floyd-Warshall algorithm calculate?

   • Minimum spanning tree
   • Single-source shortest paths
   • All-pairs shortest paths

   Hint

   Consider which type of paths it handles.

4. 4.

   True or False: Negative cycles allow for well-defined shortest paths.

   • True
   • False

   Hint

   Think about what happens to path lengths in a loop.

5. 5.

   Modify the Floyd-Warshall algorithm to handle graphs with different weight ranges or constraints. Describe the thought process and adjustments needed.

   Hint

   Think about how constraints might affect path calculations.

6. 6.

   Create a graph with four vertices and specific weights, then manually apply the Floyd-Warshall algorithm step-by-step. Illustrate the changes at each stage.

   Hint

   Keep track of which vertex is serving as an intermediary at each step.